Practival Problems:
a. Construct a Huffman code
b. Compute the sum of a large set of floating point numbers
c. Find the million largest of a billion numbers stored on a file
d. Merge many small sorted files into one large sorted file ( this problem arises in implementing a disk-based merge sort algorithm)
摘自： 《编程珠玑》 The Programming Pearls
在上述问题的解决当中，都涉及到如果快速地找出 n 个数中的最小值 这一问题：
堆就是一种能够快速找出最小(大)值的数据结构。
定义：以最小堆为例
1. 一棵完全二叉树
2. 每个节点的值都小于或等于其子节点(如果存在的话)
插入操作：
由于堆是一棵完全二叉树，所以可以采用数组来实现。
如下图，当插入1的时候，必须保证 每一个节点的值小于它的孩子的值 这一性质，
我们首先在堆的尾部插入节点 1, 然后通过 PercolateUp 这个操作，不断让节点上滤，
具体就是与节点的父亲节点比较， 如果小于父亲，则与父亲交换，继续上滤。。。
直到节点的值大于或者等于父亲的值。
复杂度是： O(height) = O(lgN)
ExtractMin()操作：删除最小值
如下图，删除最小值1
首先将堆尾部的节点4 与 节点1交换，然后堆的长度减少1；
再调用 PercolateDown(下滤)， 与上滤操作类似，使得节点4不断与它的孩子交换（孩子节点值<本身）
，知道 节点的值 <= 孩子节点的值 这一性质满足。
同样，复杂度是 O(height) = O(lgN).
// copyright @ L.J.SHOU Nov.14, 2013
#include "binary-heap.h"
#include <iostream>
using namespace std;
struct Heap
{
int capacity;
int size;
ElementType *element;
};
Heap* Initialize(int max_elements)
{//start from index 1
Heap* q = new struct Heap;
q->element = new ElementType[max_elements + 1];
q->capacity = max_elements;
q->size = 0;
q->element[0] = -0x7FFFFFF;
return q;
}
void Destroy(Heap* q)
{
delete [] q->element;
delete q;
}
void MakeEmpty(Heap* q)
{
q->size = 0;
}
void PercolateUp(Heap* q, int index)
{
int i;
ElementType x;
x = q->element[index];
for(i=index; x < q->element[i/2]; i/=2)
q->element[i] = q->element[i/2];
q->element[i] = x;
}
void PercolateDown(Heap* q, int index)
{
int i, child;
ElementType x;
x = q->element[index];
for(i=index; 2*i<=q->size; i=child)
{//find smaller child
child = 2*i;//left child
if(child != q->size && q->element[child+1] < q->element[child])
++ child;
if(x > q->element[child])
q->element[i] = q->element[child];
else
break;
}
q->element[i] = x;
}
void Insert(ElementType x, Heap* q)
{//percolate up, if < parent
if(IsFull(q)){
cerr << "Heap* is full" << endl;
return;
}
int i;
for(i = ++q->size; x < q->element[i/2]; i/=2)
q->element[i] = q->element[i/2];
q->element[i] = x;
}
ElementType DeleteMin(Heap* q)
{//percolate down, find the smaller one of childen
if(IsEmpty(q)){
cerr << "Heap* is empty" << endl;
return q->element[0];
}
ElementType last, min;
int i, child;
last = q->element[q->size --];
min = q->element[1];
for(i=1; 2*i <= q->size; i = child)
{//find the smaller child
child = 2*i;//left child
if(child != q->size && q->element[child+1] < q->element[child])
++ child;
if(last > q->element[child])
q->element[i] = q->element[child];
else
break;
}
q->element[i] = last;
return min;
}
ElementType FindMin(Heap* q)
{
if(IsEmpty(q)){
cerr << "Heap* is empty" << endl;
return q->element[0];
}
else
return q->element[1];
}
bool IsEmpty(Heap* q)
{
return (q->size == 0);
}
bool IsFull(Heap* q)
{
return (q->size == q->capacity);
}
void DecreaseKey(Heap* q, int delta, int index)
{//Percolate up
if(index < 1 || index > q->size){
cerr << "index is out of range" << endl;
return;
}
if(delta < 0){
cerr << "delta must be positive" << endl;
return;
}
q->element[index] -= delta;
PercolateUp(q, index);
}
void IncreaseKey(Heap* q, int delta, int index)
{//Percolate down
if(index < 1 || index > q->size){
cerr << "index is out of range" << endl;
return;
}
if(delta < 0)
{
cerr << "delta must be positive" << endl;
return;
}
q->element[index] += delta;
PercolateDown(q, index);
}
void Delete(Heap* q, int index)
{//DecreaseKey to infinity, and DeleteMin
DecreaseKey(q, 0x7FFF, index);
DeleteMin(q);
}
Heap* BuildHeap(int *element, int length)
{
Heap* q = new struct Heap;
q->element = element;
q->capacity = q->size = length;
for(int i=q->size/2; i>0; --i)
PercolateDown(q, i);
return q;
}
int main()
{
int a[]={11,10,9,8,7,6,5,4,3,2,1};
Heap* queue;
queue = BuildHeap(a, sizeof(a)/sizeof(int) - 1);
while(queue->size)
cout << DeleteMin(queue) << " ";
cout << endl;
delete queue;
return 0;
}