heap & max priority queue
section1: heap
0 概述
1 (二叉) 堆 是1个 数组, 可视为 完全二叉树 root: A[0]
`除 最底层 外`, 树 `完全填满: 每层 从左向右 fill`2 heap 数组 A 2个属性
(1) A.length: 数组元素数
(2) A.heapSize: 有用堆元素数
3 nodeIndex i = 0..A.length - 1 => parentIndex / lcIndex / rcIndex index
parentIndex(i) return floor( (i+1)/ 2 - 1 ) = (i+1)/ 2 - 1 lcIndex(i) return 2*(i+1) - 1 = 2*i + 1 rcIndex(i) return 2*(i+1) + 1 - 1 = 2*i + 24 应用
(1) heap sort 中 管理 information: 最大堆 A[parentIndex(i)] >= A
(2) 构造 priority queue: 最小堆 A[parentIndex(i)] <= A
(3) heap sort
1) 与 归并排序 区别 T(n) = O(n lgn) 2) 与 插入排序 区别 任何时间 只需 `常数个 额外元素空间` 存储 `暂时 data`(4) heap node 高度: node 到 leaf node 最长 simple path 上 边数
以下以 最大堆 为例
1 维护堆性子: maxHeapify(A, curIndex)
假定 curIndex 以上满足 最大堆性子
自 curIndex 向下 让 A[curIndex] 在 maxHeap 中 逐级下降, 使 curIndex 子树 重新遵照 maxHeap 性子
code [1] 求 本 curIndex.key+lc+rc 中的 maxIndex: curIndex/lcIndex/rcIndex
[2] 若 本 curIndex.key 违背 最大堆性子 => 用 maxIndex.key & maxIndex 互换 & 递归
maxHeapify(A, curIndex) // O(lgn) lcIndex = lcIndex(curIndex) rcIndex = rcIndex(curIndex) // (1) 求 本 curIndex.node+lc+rc 中的 maxIndex: curIndex/lcIndex/rcIndex maxIndex = curIndex if lcIndex <= A.heapSize && A[lcIndex] > A[curIndex] maxIndex = lcIndex if rcIndex <= A.heapSize && A[rcIndex] > A[maxIndex] maxIndex = rcIndex // (2) 若 本 curIndex.node 违背 最大堆性子 => 用 maxIndex.key & maxIndex 互换 & 递归 if maxIndex != curIndex swap(A[curIndex], A[maxIndex]) maxHeapify(A, maxIndex)2 建堆 buildMaxHeap(A)
对 A[0 .. A.length - 1 ] 自底向上(index 减小) 调 maxHeapify
A[ n/2 .. n-1 ] 均为 叶结点: 视为 只含 1 个 elem 的 heap
=> 只需对 非叶结点 A[n/2 - 1 .. 0] 自底向上(index 减小) 调 maxHeapify
———————————————————————————————————————————————————— n = A.length 叶 index: 归纳法 完全二叉数布局 ———————————————————————————————————————————————————— 0 3 1 / 2 1 2 ———————————————————————————————————————————————————— 4 2 / 3 0 1 2 3 ———————————————————————————————————————————————————— ... = n/2 .. n-1 ————————————————————————————————————————————————————buildMaxHeap(A) // O(n) A.heapSize = A.length for(int i = heapSize/2 - 1; i >= 0; --i) maxHeapify(A, i)3 heap sort: heapSort(A)
heap sort 较良好, 但 现实应用中 qiuck sort 性能通常更好
(1) 建堆 => 顶 最大
(2) heapSize - 1 次 循环
[1] 互换 顶 与 底
[2] 新底 index&index.key 均最大 => 下一趟排序去掉它: --heapSize;
[3] 新顶 (index = 0) index.key notMax => 粉碎 最大堆性子 => 对 新顶 index 调 maxHeapify(A, 0)
heapSort(A) // (n-1) * O(lgn) = O(n*lgn) buildMaxHeap(A) for( int i = heapSize - 1; i >= 1; --i) swap(A, A[0]) --A.heapSize // update heapSize maxHeapify(A, 0)section2: max priority queue: key 体现 优先级
1 insert(A, key)
1] heapSize 自增 2] 底 初始化为 最小负值: 辅助函数中 置为 key 3] increase 底.key 到 key insert(A, key) ++A.heapSize A[A.heapSize] = 负最大值 increaseKey(A, A.heapSize, key)increaseKey(A, index, key): insert 辅助函数
1) index.key 置 key => 违背 最大堆性子
2) 从 底 开始, 逐层 swap/上升(index 减小) 到 不再与 A[parentIndex] 逆序 的 位置
increaseKey(A, index, key) if key < A[index] error: "printf("new key 小于 curIndex key");" A[index] = key while(index > 1 && A[index] > A[parentIndex(index)] ) swap(A[index], A[ parentIndex(index )] ) inedx = parentIndex(index)2 extractMax(S) <-> stack 的 topAndPop()
为 使 heap 总是 从 index = 0 开始, 将 底 node(index = heapSize - 1) 挪到 顶(index = 0) & update heapSize
=> 违背 最大堆性子 -> 对 顶(index = 0) 调 maxHeapify(A, 0) 重新维护 最大堆性子
extractMax(A) if A.heapSize < 1 error: heap underflow max = A[0] // 1] - - - - - - - - - // | A[0] = A[A.heapSize - 1] // 3] | --A.heapSize // 4] update heapSize | maxHeapify(A, 0) // 5] | // | return max // 2] - - - - - - - - - 3 maxElem(S) <-> stack 的 top()
应用: OS 任务调理
(1) max priority queue 记载 各 tasks 的 优先级
(2) 某 task 完成/停止 后, scheduler 调 extractMax, 从 waiting tasks 中 选出 优先级最高 的 task 去实行
(3) 任何时间, scheduler 可调 insert, 参加 task 到 queue
section3: min priority queue
应用: 变乱驱动 模拟器
section4: priority queue 也要存 对应 obj 的 handle: ptr / index
// heap.h#ifndef _HEAP_H#define _HEAP_H#define N 5extern int heap_array[N]; extern int heapSize;int parentIndex(int i);int lcIndex(int i);int rcIndex(int i);void maxHeapify(int* parentIndex, unsigned int curIndex);void buildMaxHeap(int* p_heap_arr);void heapSort(int* p_heap_arr);void insert(int* p_heap_arr, int key);int extractMax(int* p_heap_arr);int maxElem(int* parentIndex);void printHeap(int* p_heap_arr);#endif// 二叉排序树#include <cstdio>#include <climits> // INT_MIN#include "heap.h"#define N 5void swap(int* v1, int* v2){ int tmp = *v1; *v1 = *v2; *v2 = tmp;}// Note: 末了1个数组元素 invalid, 待 插int heap[N] = {10, 20, 5, 30, 0}; int heapSize = 0;// === 3 个 index int parentIndex(int i) { return (i+1)/ 2 - 1; }int lcIndex(int i) { return 2*i + 1; }int rcIndex(int i) { return 2*i + 2; }// === 3 大函数: maxHeapify / buildMaxHeap / heapSortvoid maxHeapify(int* parentIndex, unsigned int curIndex){ // [1] int lcIndex = lcIndex(curIndex); int rcIndex = rcIndex(curIndex); // [2] int maxIndex = 0; if( lcIndex < heapSize && parentIndex[lcIndex] > parentIndex) maxIndex = lcIndex; else maxIndex = curIndex; if(rcIndex < heapSize && parentIndex[rcIndex] > parentIndex[maxIndex]) maxIndex = rcIndex; // [3] if(maxIndex != curIndex) { swap(parentIndex + curIndex, parentIndex + maxIndex); maxHeapify(parentIndex, maxIndex); }}void buildMaxHeap(int* parentIndex){ heapSize = N -1; // Note: 留 1个 插入 / 删除 position for(int i = heapSize/2 - 1; i >= 0; --i) maxHeapify(parentIndex, i);} void heapSort(int* parentIndex){ buildMaxHeap(parentIndex); for( int i = heapSize - 1; i >= 1; --i) { swap(parentIndex + i, parentIndex); --heapSize; maxHeapify(parentIndex, 0); }} // === insert & 辅助 increaseKey + extractMaxvoid increaseKey(int* parentIndex, unsigned int index, int key){ if( key < parentIndex[index]) printf("new key 小于 curIndex key"); parentIndex[index] = key; while( index > 0 && parentIndex[ parentIndex(index) ] < parentIndex[index] ) { swap( parentIndex + parentIndex(index), parentIndex + index); index = parentIndex(index); }}void insert(int* parentIndex, int key){ ++heapSize; parentIndex[heapSize - 1] = INT_MIN; increaseKey(parentIndex, heapSize - 1, key);}int maxElem(int* parentIndex){ return parentIndex[0]; }int extractMax(int* parentIndex){ if(heapSize < 0) printf("heap underflow"); int max = parentIndex[0]; parentIndex[0] = parentIndex[heapSize - 1]; --heapSize; maxHeapify(parentIndex, 0); return max;}void printHeap(int* parentIndex){ printf("---heap: \n"); for(int i = 0; i < heapSize; ++i) printf("%d ", *(parentIndex + i) ); printf("\n");}// === client #include <cstdio>#include <stdlib.h> // malloc / free#include "heap.h"// === test cases: ===void Test(int* parentIndex, int key){ buildMaxHeap(parentIndex); // 1) printHeap(parentIndex); insert(parentIndex, key); // 2) printHeap(parentIndex); int max = extractMax(parentIndex); // 3) printf("--- max: %d\n", max); printHeap(parentIndex); heapSort(parentIndex); // 4) }void Test1(){ int key = 15; Test(heap, key);}int main(){ Test1(); return 0;}
|
