首页 > 代码库 > 二叉堆
二叉堆
二叉堆
我们知道堆栈是一种LIFO（后进先出）结构，队列是一种FIFO（先进先出）结构，而二叉堆是一种最小值先出的数据结构，因此二叉堆很适合用来做排序。
二叉树的性质：二叉堆是一棵完全二叉树，且任意一个结点的键值总是小于或等于其子结点的键值，
二叉堆采用数组来存储（按广度优先遍历的顺序），而没有像普通的树结构使用指针来表示节点间的关系。
如下图所示：
如图，最小的一个元素就是数组第一个元素。
将二叉堆按最广优先遍历的顺序编号从0到N-1，根据完全二叉树的性质，则第n个结点的子结点分别是2n+1和2n+2，其父结点是(n-1)/2。并且，叶子结点的下标是从 (N-1)/2开始，一直到N-1。这样，对于数组中的任意一个元素，我们可以很方便的计算出它的父节点、孩子节点所在的位置（即数组下标）。
插入
如果要在二叉堆中插入或删除一个元素，必须保证堆性质仍能满足。
假如要在上面的二叉堆里插入一个键值为2的新元素，那只需在数组末尾加入这个元素，然后尽可能把这个元素往上挪，直到挪不动，经过了这种复杂度为Ο(logn)的操作，二叉堆还是二叉堆。如下图：
插入过程：
如上图，将键值为2的元素放在数组最后一个位置（下标为12，下标从0开始计数），
其父节点是下标为5的元素，且其键值为6>2，不满足堆性质，将两个元素交换；
现在键值为2的新元素的下标变成了5，其父节点是下标为2的元素，该元素键值为5>2，继续交换！
删除
删除操作一定是踢出数组的第一个元素，这么来第一个元素以前的位置就成了空位，我们需要把这个空位挪至叶子节点，然后把数组最后一个元素插入这个空位，把这个“空位”尽量往上挪，如下图所示：
最后意：删除和插入一样，都是O(n)的时间复杂度。
C++的一个实现：
#include <iostream>using namespace std;#define SWAP_TWO_INT(a, b) a^=b; b^=a; a^=b;class CBinaryHeap{ public: CBinaryHeap(int iSize = 100); ~CBinaryHeap(); //Return 0 means failed. int Enqueue(int iVal); int Dequeue(int &iVal); int GetMin(int &iVal); void PrintQueue(); protected: int *m_pData; int m_iSize; int m_iAmount;};CBinaryHeap::CBinaryHeap(int iSize){ m_pData = new int[iSize]; m_iSize = iSize; m_iAmount = 0;}CBinaryHeap::~CBinaryHeap(){ delete[] m_pData;}int CBinaryHeap::Enqueue(int iVal){ if (m_iAmount == m_iSize) return 0; //Put this value to the end of the array. m_pData[m_iAmount++] = iVal; int iIndex = m_iAmount - 1; while (m_pData[iIndex] < m_pData[(iIndex-1)/2]) { SWAP_TWO_INT(m_pData[iIndex], m_pData[(iIndex-1)/2]) iIndex = (iIndex-1)/2; } return 1;}int CBinaryHeap::Dequeue(int &iVal){ if(m_iAmount==0) return 0; iVal = m_pData[0]; int iIndex = 0; while (iIndex*2<m_iAmount) { int iLeft = (iIndex*2+1 < m_iAmount)?(iIndex*2+1):0; int iRight = (iIndex*2+2 < m_iAmount)?(iIndex*2+2):0; if(iLeft && iRight) // Both left and right exists. { if(m_pData[iLeft]<m_pData[iRight]) { SWAP_TWO_INT(m_pData[iIndex], m_pData[iLeft]) iIndex = iLeft; } else { SWAP_TWO_INT(m_pData[iIndex], m_pData[iRight]) iIndex = iRight; } } else if(iLeft) //The iRight must be 0 { SWAP_TWO_INT(m_pData[iIndex], m_pData[iLeft]) iIndex = iLeft; break; } else { break; } } //Move the last element to the blank position. //Of course, if it is the blank one, forget it. if(iIndex!=m_iAmount-1) { m_pData[iIndex] = m_pData[m_iAmount-1]; //Try to move this element to the top as high as possible. while(m_pData[iIndex] < m_pData[(iIndex-1)/2]) { //Swap the two value SWAP_TWO_INT(m_pData[iIndex], m_pData[(iIndex-1)/2]) iIndex = (iIndex-1)/2; } } --m_iAmount; return 1;}int CBinaryHeap::GetMin(int &iVal){ if (m_iAmount==0) return 0; iVal = m_pData[0]; return 1;}void CBinaryHeap::PrintQueue(){ int i; for (i=0; i<m_iAmount; i++) { cout<<m_pData[i]<<"\t"; } cout<<endl;}int main(){ int iVal; CBinaryHeap bh; bh.Enqueue(4); bh.Enqueue(1); bh.Enqueue(3); bh.Enqueue(2); bh.Enqueue(6); bh.Enqueue(5); bh.PrintQueue(); bh.Dequeue(iVal); bh.Dequeue(iVal); bh.PrintQueue(); return 0;}
最大堆：父结点的键值总是大于或等于任何一个子结点的键值；最大堆常用于排序算法。
最小堆：父结点的键值总是小于或等于任何一个子结点的键值；最小堆常用于优先队列。
二叉堆