網站首頁 編程語言 正文
一、堆的概念
(1)定義
如果有一個關鍵碼的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數組中,并滿足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,則稱為小堆(或大堆)。將根節點最大的堆叫做最大堆或大根堆,根節點最小的堆叫做最小堆或小根堆。
(2)性質
1.堆中某個節點的值總是不大于或不小于其父節點的值;
2.堆總是一棵完全二叉樹。
(3)小根堆示例圖
二、堆的實現
(1)堆的創建
例如:int a[ ] = {1,5,3,8,7,6};
a.初始化堆
b.交換3 和 6
c.交換5 和 8
d.交換1 和 8
調整1和8的位置,8的左子樹構成的結構被破壞,每一次調整元素的時候都有可能破壞其子堆的結構。
(2)堆的插入
先將數字插入到數組的尾部,然后進行向上調整算法,直到滿足堆。
例如:在一個堆中插入80
(3)堆的刪除
刪除堆是刪除堆頂的數據,將堆頂的數據根最后一個數據一換,然后刪除數組最后一個數據,再進行向下調整算法。
三、堆的代碼實現
#include"common.h"
#define HeapDataType int
typedef struct Heap
{
HeapDataType *base;
int capacity;
int size;
}Heap;
void HeapInit(Heap *php, int n);
void MinHeapInsert(Heap *php, HeapDataType x);
HeapDataType MinHeapRemove(Heap *php);
bool HeapEmpty(Heap *php);
void HeapPrint(Heap *php);
void HeapSort(Heap *php);
void AdjustUp(HeapDataType *base, int start);
void AdjustDown(HeapDataType *base, int start, int n);
void HeapInit(Heap *php, int n)
{
assert(php != NULL);
php->base = (HeapDataType*)malloc(sizeof(HeapDataType) * n);
assert(php->base != NULL);
php->capacity = n;
php->size = 0;
}
bool HeapEmpty(Heap *php)
{
assert(php != NULL);
return php->size == 0;
}
void MinHeapInsert(Heap *php, HeapDataType x)
{
assert(php != NULL);
if(php->size < php->capacity)
{
php->base[php->size] = x;
AdjustUp(php->base, php->size);
php->size++;
}
}
HeapDataType MinHeapRemove(Heap *php)
{
assert(php != NULL);
assert(php->size > 0);
int heaptop_val = php->base[0];
php->size--;
php->base[0] = php->base[php->size];
AdjustDown(php->base, 0, php->size);
return heaptop_val;
}
void HeapPrint(Heap *php)
{
for(int i=0; i<php->size; ++i)
printf("%d ", php->base[i]);
printf("\n");
}
void AdjustUp(HeapDataType *base, int start)
{
int j = start;
int i = (j-1)/2;
HeapDataType tmp = base[j];
while(j > 0)
{
if(tmp < base[i])
{
base[j] = base[i];
j = i;
i = (j-1)/2;
}
else
break;
}
base[j] = tmp;
}
void AdjustDown(HeapDataType *base, int start, int n)
{
int i = start;
int j = 2*i + 1;
while(j < n)
{
if(j+1<n && base[j]>base[j+1])
j++;
if(base[i] > base[j])
{
Swap(&base[i], &base[j]);
i = j;
j = 2*i + 1;
}
else
break;
}
}
void HeapSort(Heap *php, int ar[], int n)
{
for(int i=0; i<n; ++i)
php->base[i] = ar[i];
php->size = n;
int curpos = n/2 - 1;
while(curpos >= 0)
{
AdjustDown(php->base, curpos, n);
curpos--;
}
int end = n-1;
while(end > 0)
{
Swap(&php->base[0], &php->base[end]);
AdjustDown(php->base, 0, end);
end--;
}
int k = php->size - 1;
for(int i=0; i<n; ++i)
{
ar[i] = php->base[k--];
}
}
原文鏈接:https://blog.csdn.net/Onion_521257/article/details/106408917
相關推薦
- 2022-05-25 Properties的遍歷幾種方式
- 2024-03-03 ElementUi中el-cascader表單驗證問題
- 2022-10-27 python使用pika庫調用rabbitmq交換機模式詳解_python
- 2022-07-01 使用Python讀寫多個sheet文件_python
- 2022-07-21 微信小程序--動態設置導航欄顏色
- 2022-12-30 React淺析Fragments使用方法_React
- 2023-07-05 Redis性能瓶頸:如何優化大key問題?
- 2022-09-27 linux?shell中Grep命令查找多個字符串(grep同時匹配多個關鍵字或任意關鍵字)_lin
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版(
- Linux 中運行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符,流程控制 Flo
- 1. Int 和Integer 的區別,Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤:Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串(SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列,發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支