最近再次复习编写堆排,于是重新梳理了一下。之前也写过堆排的代码:堆排Heap Sort
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; }