堆排Heap Sort（2）–堆的插入和删除

最近再次复习编写堆排，于是重新梳理了一下。之前也写过堆排的代码：堆排Heap Sort

[c language=”++”]
vector<int> heap;
int size;

void push(int x)
{
int i = size++;
int p = (i – 1) / 2;
while (x>heap[p])
{
heap[i] = heap[p];
if (i == 0) break;
i = p;
p = (i – 1) / 2;
}
heap[i] = x;
}

void pop()
{
int bottom = heap[size – 1];
int i = 0;
int a = 2 * i + 1, b = 2 * i + 2;
size–;
while (a<size)
{
if (b<size&&heap[a]<heap[b]) a = b;
if (bottom<heap[a])
heap[i] = heap[a];
else break;
i = a;
a = 2 * i + 1;
b = 2 * i + 2;
}
heap[i] = bottom;
}
[/c]