結(jié)構(gòu)
完全二叉樹（并不是滿二叉樹）
底層是數(shù)組
分類
- 最大堆
每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值 - 最小堆
每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值
最大堆性質(zhì)
父節(jié)點大于所有子節(jié)點瓮恭，但是左右子節(jié)點
功能:
維護(hù)動態(tài)數(shù)據(jù)的最大最小值,可以考慮使用堆
調(diào)整堆的時間復(fù)雜度O(logk)
堆的操作(以小頂堆為例)
https://www.acwing.com/blog/content/308/
heap[++size] = x;up(size); //插入一個數(shù)
heap[1]; //求最小值
heap[1] = heap[size];size--;down(1); //刪除最小值
heap[k] = heap[size];size--;down(k);up(k); //刪除任意一個元素
heap[k] = x;down(k);up[k]; //修改任意一個元素
- down和up的時間復(fù)雜度為O(logn)最多交換深度h - 1次,h為n的log函數(shù)
down()
循環(huán)down
- 圖1 循環(huán)down,注意是fa的左側(cè)子節(jié)點存在,即<heapSize的時候.其實還是遞歸比較好理解
- 注意else的break;
- 注意nums[ minmum ] 而不是u,因為兩個minmum可能因為賦值會不一樣
void down(vector<int>& nums, int u, int heapSize) {
//圖1 循環(huán)down,注意是fa的左側(cè)子節(jié)點存在,即<heapSize的時候.其實還是遞歸比較好理解
//注意else的break;
//注意nums[ minmum ] 而不是u,因為兩個minmum可能因為賦值會不一樣
while (u * 2 + 1 < heapSize) {
int l = u * 2 + 1, r = u * 2 + 2, minmum = u;
if (l < heapSize && nums[l] < nums[minmum]) {
minmum = l;
}
if (r < heapSize && nums[r] < nums[minmum]) {
minmum = r;
}
if (u != minmum) {
swap(nums[u], nums[minmum]);
u = minmum;
}
else {
break;
}
}
}
圖1
遞歸down
void down(vector<int>& nums, int u, int heapSize) {
// 遞歸down
int l = u * 2 + 1, r = u * 2 + 2, minmum = u;
if (l < heapSize && nums[l] < nums[minmum]) {
minmum = l;
}
if (r < heapSize && nums[r] < nums[minmum]) {
minmum = r;
}
if (u != minmum) {
swap(nums[u], nums[minmum]);
down(nums, minmum, heapSize);
}
}
up()
循環(huán)up
void up(vector<int>& nums, int u, int heapSize) {
while (u && nums[(u - 1) / 2] > nums[u]) {
swap(nums[(u - 1) / 2], nums[u]);
u = u - 1 / 2;
}
}
遞歸up
void up(vector<int>& nums, int u, int heapSize) {
int fa = (u - 1) / 2;
if (u != 0 && nums[fa] > nums[u]) {
swap(nums[fa], nums[u]);
up(nums, fa, heapSize);
}
}
建堆
https://www.acwing.com/activity/content/code/content/493331/
-
時間復(fù)雜度為O(n),為什么?
void buildMinHeap(vector<int>& nums, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
down(nums, i, heapSize);
}
}
heapify
使得數(shù)組“堆有序”
- 一定是全部有序嗎盒音？為什么
不是沥邻，無法確定子節(jié)點左右大小 -
那堆排序如何實現(xiàn)腔呜？
小頂堆,交換top和rear的位置,size--;down(top).這樣數(shù)組從大到小排列
交換n次,每次down的時間復(fù)雜度為O(logn)時間復(fù)雜度為O(nlogn)
較小值下沉
void maxHeapify(vector<int>& a, int i, int heapsize) {
//如果是基1的,那么l = i * 2, r = i * 2 + 1
int l = i * 2 + 1, r = i * 2 + 2, largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
//交換i和字節(jié)中的最大值
swap(a[largest], a[i]);
//較小值下沉
maxHeapify(a, largest, heapSize);
}
}
buildheap
void buildMaxHeap(vector<int>& a, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}
- heapsize不減的話一定會多做兩次heapify敬察。（其實問題不大）
