数据结构基础(五)

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)

1. Method 1
   • heap = Initialize(…)
   • N times of Insertion(seq[i], heap)
   • $O(N\log N)$
2. 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