编程珠玑（2）第十四章学习笔记之“堆”

珠玑（2）第十四章学习笔记之“堆”"/>

编程珠玑（2）第十四章学习笔记之“堆”

本章主要介绍“堆”和“优先队列”数据结构的使用。

堆可分为大根堆和小根堆。堆是某个节点的值总是不大于（大根堆）或不小于（小根堆）其父节点的完全树。常见的堆有二叉堆和斐波那契堆，本章讲的是二叉堆。

由于二叉堆是完全二叉树，所以我们在建堆的时候可以考虑用C++中的vector来作为存储结构。

堆有两个比较重要的操作：插入和删除。插入时，我们一般将新插入的元素放在末尾，这时需要做向上调整；删除时一般是删除“根”节点元素，这时需要做向下调整，以确保堆的性质。

所谓优先队列是不同于先进先出的普通队列，而是每次从队列中取出具有最高优先权的元素。根据优先队列这一特点（每次取出最高优先权的元素），我们可以很自然地想到用堆来实现优先队列。补充一句：优先队列是一个非常有用的数据结构，在实际的编程中常常用到，在C++中有模板库，可以直接调用。

具体实现见代码：

#include<stdio.h>
#include<vector>
#include<stdexcept>
using namespace std;//堆数据结构的实现（小根堆）
template <typename T>
class Heap
{public:Heap(){}Heap(T elements[], int arraySize){for(int i=0; i<arraySize; i++){add(elements[i]);}}void add(T element){int currentIndex;v.push_back(element);currentIndex = v.size()-1;while(currentIndex > 0){int parentIndex = (currentIndex - 1) / 2;if(v[parentIndex] > v[currentIndex]){T temp = v[parentIndex];v[parentIndex] = v[currentIndex];v[currentIndex] = temp;}else{break;}currentIndex = parentIndex;}}T remove() throw(runtime_error){if(v.size() == 0){throw runtime_error("Heap is empty");}T removedElement = v[0];v[0] = v[v.size()-1];v.pop_back();int currentIndex = 0;while(currentIndex < v.size()){int leftChildIndex = 2 * currentIndex + 1;int rightChildIndex = 2 * currentIndex + 2;if(leftChildIndex >= v.size())break;int minIndex = leftChildIndex;if(rightChildIndex < v.size()){if(v[minIndex] > v[rightChildIndex]){minIndex = rightChildIndex;}}if(v[currentIndex] > v[minIndex]){T temp = v[currentIndex];v[currentIndex] = v[minIndex];v[minIndex] = temp;currentIndex = minIndex;}else{break;}}return removedElement;}int getSize(){return v.size();}private:vector<T> v;
};//利用堆实现的优先队列（每次弹出最小的元素）
template <typename T>
class PriorityQueue
{
public:PriorityQueue(){}void enqueue(T element){heap.add(element);}T dequeue() throw (runtime_error){heap.remove();}int getSize(){return heap.getSize();}private:Heap<T> heap;
};//堆排序的实现
void heapAdjust(int a[], int s, int m){ //向下调整，建立大根堆int temp = a[s];int i, j;for(j=s*2; j<=m; j*=2){if(j<m && a[j]<a[j+1]){j++;}if(temp >= a[j]){break;}a[s] = a[j];s = j;}a[s] = temp;
}void HeapSort(int a[], int n)
{int i;for(i=(n-1)/2; i>=0; i--){heapAdjust(a, i, n-1);}for(i=n-1; i>0; i--){int temp = a[i];a[i] = a[0];a[0] = temp;heapAdjust(a, 0, i-1);}
}int main()
{int a[7] = {12, 34, 11, 13, 29, 48, 35};HeapSort(a, 7);for(int i=0; i<7; i++){printf("%d ", a[i]);}return 0;
}