資料結構之（二叉）堆

（二叉）堆是一個數組，是一顆近似完全二叉樹，分為大頂堆&小頂堆。表示堆的數組A有兩個屬性：（1）A.length表示數組元素的個數；（2）A.heap-size表示有多少個堆元素存儲在數組A中。更多的關于堆的性質的介紹：算法導論第三版：p85-p89、程式設計珠玑：p141-p145。

堆的操作主要包括堆插入、堆删除兩個，而堆插入設計到SiftUp操作（自底向上調整），堆删除涉及到SiftDown操作（自頂向下調整，大頂堆時對應算法導論上的MAX-HEAPIFY操作）。

下面是大頂堆和小頂堆的基本操作的C++的實作：

//heap.h
#pragma once

template<class T>
class Heap
{
public:
	Heap(const int nmax = 100) : max_size(nmax)
	{
		arr = new T[max_size];
		size = 0;
	}
	virtual ~Heap() {delete []arr;}
	void Insert(const T &e);	
	void Delete(const T &e);
	int Search(const T &e) const;
	void Print() const;
protected:
	T *arr;
	const int max_size;	//max array elements
	int size;	//size of heap
	virtual void SiftDown(int i) = 0;	//adjust from up to down
	virtual void SiftUp(int i) = 0;	//adjust from down to up
};

template<class T>
void Heap<T>::Insert(const T &e)
{
	if (size == max_size)
		return;
	arr[size++] = e;  //将新插入的元素添加在最後位置并增加size
	SiftUp(size - 1);  //數組下标從0開始
}

template<class T>
void Heap<T>::Delete(const T &e)
{
	int pos = Search(e);
	if (pos == -1)
		return;
	arr[pos] =	arr[--size];	//用最後的元素填充pos位置的元素，并減少size
	SiftDown(pos);
}

template<class T>
int Heap<T>::Search(const T &e)const
{
	for (int i = 0; i < size; i++)
		if (arr[i] == e)
			return i;
	return -1;
}

template<class T>
void Heap<T>::Print()const
{
	for (int i = 0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}
           

最大堆：maxHeap.h

//maxHeap.h
#pragma once
#include "heap.h"
#include <iostream>
using std::cout;
using std::endl;

template<class T>
class MaxHeap : public Heap<T>
{
public:
	MaxHeap(const int nmax = 100) : Heap(nmax) {}	
	~MaxHeap() {}
private:
	virtual void SiftDown(int i);	//adjust from up to down
	virtual void SiftUp(int i);	//adjust from down to up
};

template<class T>	
void MaxHeap<T>::SiftDown(int i)
{	
	//已知arr[i,...,size)除arr[i]之外均滿足大頂堆的定義,本函數向下調整arr[i]
	//使得在具有size個結點的堆中,以i為下标的根節點的子樹重新遵循最大堆的性質
	//size為節點總數，從0開始計算，i節點的子節點為 2*i+1, 2*i+2
	int tmp, j;
	j = 2 * i + 1;//結點i的左孩子下标
	tmp = arr[i];
	while (j < size)
	{
		if (j + 1 < size && arr[j + 1] > arr[j])//找左右孩子中最大的
			j++;
		if (arr[j] <= tmp)	 //	父結點tmp=arr[i]比孩子結點arr[j]大
			break;
		arr[i] = arr[j];//把較大的子結點往上移動,替換它的父結點
		i = j;
		j = 2 * i + 1;
	}
	arr[i] = tmp;
}
template<class T>
void MaxHeap<T>::SiftUp(int i)
{
	//新加入結點i,原本arr[0, size）滿足堆性質,向上調整使得[0, size+1)滿足最大堆性質
	int j, tmp;
	j = (i - 1) / 2; //i的父結點
	tmp = arr[i];
	while (j >= 0 && i != 0)
	{
		if (arr[j] >= tmp)	//父節點arr[j]比子結點tmp = arr[i]大
			break;
		arr[i] = arr[j];//把較小的父結點往下移動,替換它的子結點
		i = j;
		j = (i - 1) / 2;
	}
	arr[i] = tmp;
}
           

最小堆：minHeap.h

//minHeap.h
#pragma once
#include "heap.h"
#include <iostream>
using std::cout;
using std::endl;

template<class T>
class MinHeap : public Heap<T>
{
public:
	MinHeap(const int max_size = 100) : Heap(max_size) {}
	~MinHeap(){}
private:
	virtual void SiftDown(int i);	
	virtual void SiftUp(int i);
};

template<class T>
void MinHeap<T>::SiftDown(int i)
{
	//已知arr[i,...,size)除arr[i]之外均滿足小頂堆的定義,本函數向下調整arr[i]
	//使得在具有size個結點的堆中,以i為下标的根節點的子樹重新遵循最大堆的性質
	//size為節點總數，從0開始計算，i節點的子節點為 2*i+1, 2*i+2
	int j, tmp;
	j = 2 * i + 1;	//左孩子
	tmp = arr[i];
	while (j < size )
	{
		if (j + 1 < size && arr[j + 1] < arr[j])   //找左右孩子中最小的
			j++;
		if (arr[j] >= tmp) //	父結點tmp=arr[i]比孩子結點arr[j]小
			break;
		arr[i] = arr[j];  //把較小的子結點往上移動,替換它的父結點
		i = j;
		j = 2 * i + 1;
	}
	arr[i] = tmp;
}

template<class T>
void MinHeap<T>::SiftUp(int i)
{
	int j, tmp;
	j = (i - 1) / 2;  //父結點
	tmp = arr[i];
	while (j >= 0 && i != 0)
	{
		if (arr[j] <= tmp)	//父節點arr[j]比子結點tmp = arr[i]小
			break;
		arr[i] = arr[j];   //把較大的父結點往下移動,替換它的子結點
		i = j;
		j = (i - 1) / 2;
	}
	arr[i] = tmp;
}
           

測試代碼：

#include "maxHeap.h"
#include "minHeap.h"

int main()
{
	int a[12] = {15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1};
	MaxHeap<int> maxheap(20);
	MinHeap<int> minheap(20);
	for (int i = 0; i < 12; i++)
		maxheap.Insert(a[i]);	 //向上調整
	maxheap.Print();
	maxheap.Delete(4);	 //向下調整
	maxheap.Print();

	for (int i = 0; i < 12; i++)
		minheap.Insert(a[i]);	 //向上調整
	minheap.Print();
	minheap.Delete(4);	 //向下調整
	minheap.Print();
	getchar();
	return 0;
}
           

這裡用的是插入的方法建堆：最壞情況下，建立一個包含n個元素的堆的時間複雜度是O（nlgn），大theta。

下一篇文中的堆排序，可以線上性時間O（n）内，把一個無需數組構造成一個最大堆。

一般地，還要k叉堆：算法導論第三版p93。

利用堆可以實作：堆排序、優先隊列。在Dijkstra算法中： EXTRACT-MIN(Q) 操作，就可以先建立最小堆，然後從最小隊列中，每次抽取最小結點（參考 最短路徑之Dijkstra算法 一文的參考資料連結）。

此外，堆還可以用于：海量資料中選擇前k個最大（最小）的數。

思想：在一個很大的無序數組裡面選擇前k個最大（最小）的資料，最直覺的做法是把數組裡面的資料全部排好序，然後輸出前面最大（最小）的k個資料。但是，排序最好需要O(nlogn)的時間，而且我們不需要前k個最大（最小）的元素是有序的。這個時候我們可以建立k個元素的最小堆(得出前k個最大值)或者最大堆(得到前k個最小值)，我們隻需要周遊一遍數組，在把元素插入到堆中去隻需要logk的時間，這個速度是很樂觀的。利用堆得出前k個最大（最小）元素特别适合海量資料的處理。

參考資料：算法導論第三版：p85-p89、程式設計珠玑：p141-p145