数据结构----堆 ( Heap )

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. 每个节点的值都小于或等于其子节点(如果存在的话)

数据结构----堆 ( Heap )


插入操作:

由于堆是一棵完全二叉树,所以可以采用数组来实现。

如下图,当插入1的时候,必须保证 每一个节点的值小于它的孩子的值 这一性质,

我们首先在堆的尾部插入节点 1, 然后通过 PercolateUp 这个操作,不断让节点上滤,

具体就是与节点的父亲节点比较, 如果小于父亲,则与父亲交换,继续上滤。。。

直到节点的值大于或者等于父亲的值。

复杂度是: O(height) = O(lgN)

数据结构----堆 ( Heap )


ExtractMin()操作:删除最小值

如下图,删除最小值1

首先将堆尾部的节点4 与 节点1交换,然后堆的长度减少1;

再调用 PercolateDown(下滤), 与上滤操作类似,使得节点4不断与它的孩子交换(孩子节点值<本身)

,知道 节点的值 <= 孩子节点的值 这一性质满足。

同样,复杂度是 O(height) = O(lgN).

数据结构----堆 ( Heap )


// 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;
}


数据结构----堆 ( Heap )

上一篇:迟到的2013年总结


下一篇:iOS显示PDF