数据结构基础(五)

Chapter 4 Heap

Heap is a kind of priority_queue(PQ), which guarantees that the head node is the largest / smallest one

ADT

Operations

PQ Initialize(int maxElem)
void Insert(ElemType key, PQ heap)
ElemType DeleteMin(PQ heap)
ElemType FindMin(PQ heap)

Simple Implementations

Array
Linked List
Ordered Array
Ordered Linked List
BST

Binary Heap

Structure Property

Heap is a fulfilled complete binary tree

完全二叉树 complete binary tree: 除了最后一层全部填满

$h=\mathrm{int}(\log N)$

完美二叉树 perfect binary tree: 最后一层也全部填满

Array Representation

put a complete tree in a array of (N + 1) length without array[0] by level-order traversal

Lemma

For any node with index $i$ :

$parent(i)=\begin{cases} i//2,&\mathrm{if}\ i\ne 1\\ \mathrm{None},&\mathrm{if}\ i= 1\\ \end{cases}$

$left\_child(i)=\begin{cases} 2i,&\mathrm{if}\ 2i\le n\\ \mathrm{None},&\mathrm{if}\ 2i>n\\ \end{cases}$

$right\_child(i)=\begin{cases} 2i+1,&\mathrm{if}\ 2i+1\ge n\\ \mathrm{None},&\mathrm{if}\ 2i+1>n\\ \end{cases}$

typedef int ElemType;
const int minData = 0x80000000;

typedef struct{
    int capacity, size;
    ElemType* elems;
} HeapStruct;
typedef HeapStruct* Priority_Queue;

Priority_Queue Initialize(int maxElem){
    Priority_Queue heap;
    heap = (Priority_Queue)malloc(sizeof(HeapStruct));
    heap->elems = (ElemType*)malloc((maxElem + 1) * sizeof(ElemType));
    heap->capacity = maxElem;
    heap->size = 0;
    heap->elems[0] = minData;
    return heap;
}

哨兵 sentinel: 哨兵是小根堆的最小值或大根堆的最大值, 并不是真实存在的, 而是虚拟的, 防止越界
小根堆 min heap: 父节点小于等于子节点
大根堆 max heap: 父节点大于等于子节点

Basic Heap Operations

Insertion

Percolate up
Insert
$O(\log N)$

void Insertion(ElemType key, PriorityQueue heap){
    if(heap->capacity == heap->size){
        return;
    }
    ++heap->size;
    int i = heap->size;
    while(heap->elems[i / 2] > key){    // Percolate up
        heap->elems[i] = heap->elems[i / 2];
        i /= 2;
    }
    heap->elems[i] = key;   // Insert
}

DeleteMin

Move back to top
Percolate down

ElemType DeleteMin(PriorityQueue heap){
    if(heap->size == 0) return heap->elems[0];
    ElemType minElem, lastElem;
    minElem = heap->elems[1];
    lastElem = heap->elems[heap->size]; // Move back to top
    --(heap->size);
    int i, child;
    for(i = 1; 2 * i < heap->size; i = child){  // Percolate down
        child = 2 * i;
        if(child < heap->size && heap->elems[child + 1] < heap->elems[child]){
            ++child;
        }
        if(lastElem > heap->elems[child]){
            heap->elems[i] = heap->elems[child];
        }
        else{
            break;
        }
    }
    heap->elems[i] = lastElem;
    return minElem;
}

Other Heap Operations

DecreaseKey(int position, unsigned delta, PQ heap)

Decrease
Percolate up

IncreaseKey(int position, unsigned delta, PQ heap)

Increase
Percolate down

Delete(int positon, PQ heap)

Decrease(position, INF, heap)
DeleteMin(heap)

BuildHeap(Elem* seq, PQ heap)

Method 1
- heap = Initialize(…)
- N times of Insertion(seq[i], heap)
- $O(N\log N)$
Methos 2
- Shift seq to a complete tree
- $\log N$ times of precolate down from the last but one level
- $O(N)$

Theorem: for a perfert binary tree og height $h$ , the sum of the heights of the nodes is $2^{h+1}-1-(h+1)$

Applications of Priority Queue

[Eg] Find the $k$ th largest / smallest element from N elements

d-Heaps

the time complexity of Insertion of d-heaps decreases to $O(\log_dN)$ ; but DeleteMin may increase to $O(d\log_dN)$

C++

Using C++ STL can help to implement heaps

#include<vector>
#include<iostream>
#include<queue>
typedef std::priority_queue<int> maxPQ; // max heap
typedef std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;    // min heap

int main(){
    maxPQ maxHeap;
    minPQ minHeap;
    std::vector<int> vec({5, 2, 6, 1, 7, 9});
    for(auto i:vec){
        maxHeap.push(i);
        minHeap.push(i);
    }
    std::cout<<maxHeap.top()<<std::endl;
    std::cout<<minHeap.top()<<std::endl;

    maxHeap.pop();
    minHeap.pop();

    std::cout<<maxHeap.top()<<std::endl;
    std::cout<<minHeap.top()<<std::endl;
}
/*
output:
9
1
7
2
*/

在 STL 中, priority_queue 被称为容器适配器, 因此他没有自己的 ADT 实现, 需要依赖既有的容器, 比如 vector, deque 等等
因此 priority_queue 的完整声明如下:
priority_queue<ElemType, Container, CompareFunc>

ElemType: 数据类型
Container: 容器类型, 默认为 vector
CompareFunc: 比较所用的函数对象, 默认为 less(大根堆), 可选 greater(小根堆), 本质上是对 operator() 的重载

然而实际上默认的 greater 和 less 就是对 operator< 的调用, 因此可以直接重载 ElemType 的 operator< 实现自定义排序方式

例如以下的代码就对自定义类 Node 实现了小根堆

struct Node{
    int negaVal;
};

bool operator< (const Node x, const Node y){
    return -(y.negaVal - x.negaVal);
}

std::priority_queue<Node, std::vector<Node>> heap;

int main(){
    Node x, y, z;
    x.negaVal = 4, y.negaVal = 6, z.negaVal = 3;

    heap.push(x);
    heap.push(y);
    heap.push(z);

    std::cout<<heap.top().negaVal<<std::endl;
}
// output: 3