数据结构 - 堆

// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int l = 2*i + 1; // left = 2*i + 1
    int r = 2*i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
	largest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
	largest = r;

    // If largest is not root
    if (largest != i) {
	swap(arr[i], arr[largest]);

	// Recursively heapify the affected sub-tree
	heapify(arr, n, largest);
    }
}

#include <functional>
#include <queue>
#include <vector>
#include <iostream>

template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
	std::cout << q.top() << " ";
	q.pop();
    }
    std::cout << '\n';
}

int main() {
    std::priority_queue<int> q;

    for(int n : {1,8,5,6,3,4,0,9,7,2})
	q.push(n);

    print_queue(q);

    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;

    for(int n : {1,8,5,6,3,4,0,9,7,2})
	q2.push(n);

    print_queue(q2);

    // Using lambda to compare elements.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1);};
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);

    for(int n : {1,8,5,6,3,4,0,9,7,2})
	q3.push(n);

    print_queue(q3);

    return 0;
}

procedure heapsort(a, count) is
    input: an unordered array a of length count

    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end <-- count - 1
    while end > 0 do
	(a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
	swap(a[end], a[0])
	(the heap size is reduced by one)
	end <-- end - 1
	(the swap ruined the heap property, so restore it)
	siftDown(a, 0, end)