C++手工实现heap【小顶堆】pop push操作

手工写了小顶堆的pop push及top的操作实现。

• top的实现
  因为小顶堆每次取出的元素，是最小值，所以我们只需要保持顶部元素为最小，top内部返回顶部元素（根节点）
• push的实现
  1.将元素插入到末尾
  2.将元素与父节点进行对比，如果小于那么就置换，大于就退出
  3.这个节点为最高节点退出循环
• pop的实现
  1.比较子左右孩子节点，如果左小于右，那么右就不要改动；同理，右小于左，那么左不用改动。
  2.上一步选出最小的节点 替换父亲节点。
  3.重复第1步骤，循环，单判断孩子节点是否为叶节点，如果为叶节点，那么就直接让最后一个元素进行替换空缺位置。也就是叶节点的父亲节点一定为元素最后一位。

#include<stdio.h>
#include<vector>
#include<iostream>
#include<math.h>

using namespace std;

class CMyHeap
{
public:
	int m_nCount;
	vector<int> m_Ary;
	void push(int nVal)
	{
		m_Ary.push_back(nVal);
		m_nCount++;
		int nIndex = m_nCount;
		int nParent = nIndex / 2;
		while (nIndex!=1)
		{
			if (m_Ary[nIndex]<m_Ary[nParent])
			{
				int nTemp = m_Ary[nParent];
				m_Ary[nParent] = m_Ary[nIndex];
				m_Ary[nIndex] = nTemp;
			}
			else
			{
				return;
			}
			nIndex = nParent;
			nParent = nIndex / 2;
		}
	}
	void pop()
	{
		int nLine = int((log(m_nCount) / log(2)));//计算有多少层
		int nLineMax = pow(2, nLine);//标志数，一旦大于等于这个数，就为叶节点了
		int nParent = 1;
		int nLeftKid = 2 * nParent;
		int nRightKid = 2 * nParent + 1;
		int nFinalKid = 0;
		//状态机原理
		while (1)
		{
			if (nFinalKid >= nLineMax)//如果到最后一层，直接末尾元素替换
			{
				m_Ary[nParent] = m_Ary[m_nCount];
				break;
			}
			else if (m_Ary[nLeftKid]<=m_Ary[nRightKid])
			{
				m_Ary[nParent] = m_Ary[nLeftKid];
				nParent = nLeftKid;
				nLeftKid = nParent * 2;
				nRightKid = 2 * nParent + 1;
				nFinalKid = nLeftKid;
			}
			else if (m_Ary[nLeftKid]>=m_Ary[nRightKid])
			{
				m_Ary[nParent] = m_Ary[nRightKid];
				nParent = nRightKid;
				nRightKid = 2 * nParent + 1;
				nLeftKid = 2 * nParent;
				nFinalKid = nLeftKid;
			}
		}
		m_nCount--;
	}
	bool empty()
    {
		return m_nCount==0?true:false;
	}
	int top()
	{
		return m_Ary[1];
	}
	CMyHeap() :m_nCount(0)
	{
		m_Ary.push_back(0);
	}
	virtual ~CMyHeap()
	{

	}
};

int main(int argc, char* argv[])
{
	CMyHeap myheap;
	int nValue = 0;
	//测试1000随机数字 前100个
	for (size_t i = 0; i < 1000; i++)
	{
		nValue = rand() % 10000;
		myheap.push(nValue);
	}
	for (size_t i = 0; i < 100; i++)
	{
		cout << myheap.top() << endl;
		myheap.pop();
	}
	return 0;
}