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 + 2

4 应用

(1) heap sort 中 管理 information: 最大堆 A[parentIndex(i)] >= A[i]

(2) 构造 priority queue: 最小堆 A[parentIndex(i)] <= A[i]

(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[i], 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 5
extern 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 5

void 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 / heapSort
void 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[i])
        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 + extractMax
void 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;
}

image.png

image.png