这里给出的是最小二叉堆
左儿子结点编号是自己编号的 x 2 + 1
右儿子结点编号是自己编号的 x 2 + 2
在插入元素的时候先插入到末尾,然后向上比较,如果父节点的值大于新元素的值就交换,直到父节点小于新元素。
在删除元素的时候,先取出根节点的值,然后将末尾元素提到根节点,再向下比较。
#include <cstdio>
using namespace std;
const int MAXN = 1000000 + 7;
int heap[MAXN], sz = 0;
void push( int x )
{
int i = sz ++; // 自己节点的编号
while(i > 0)
{
int p = (i - 1) / 2; // 取的父节点的编号
if(heap[p] <= x) // 如果已经没有大小颠倒则退出
break;
heap[i] = heap[p]; // 把父节点下移,子节点上移
i = p;
}
heap[i] = x;
}
int pop()
{
int ret = heap[0]; // 要取出的值
int x = heap[--sz];
// 从根节点开始向下交换
int i = 0;
while(i * 2 + 1 < sz)
{
int a = i * 2 + 1;
int b = i * 2 + 2;
if(b < sz && heap[b] < heap[a]) // 比较两个子节点的值,取较小的一个
a = b;
if(heap[a] >= x)
break;
heap[i] = heap[a]; // 把儿子结点的值上移
i = a;
}
heap[i] = x;
return ret;
}
int main()
{
return 0;
}