Pseudcode
1 function heapSort(a, count) is
2 input: an unordered array a of length count
3
4 (first place a in max-heap order)
5 heapify(a, count)
6
7 end := count-1 //in languages with zero-based arrays the children are 2*i+1 and 2*i+2
8 while end > 0 do
9 (swap the root(maximum value) of the heap with the last element of the heap)
10 swap(a[end], a[0])
11 (put the heap back in max-heap order)
12 siftDown(a, 0, end-1)
13 (decrease the size of the heap by one so that the previous max value will
14 stay in its proper placement)
15 end := end - 1
16
17 function heapify(a, count) is
18 (start is assigned the index in a of the last parent node)
19 start := count / 2 - 1
20
21 while start ≥ 0 do
22 (sift down the node at index start to the proper place such that all nodes below
23 the start index are in heap order)
24 siftDown(a, start, count-1)
25 start := start - 1
26 (after sifting down the root all nodes/elements are in heap order)
27
28 function siftDown(a, start, end) is
29 input: end represents the limit of how far down the heap
30 to sift.
31 root := start
32
33 while root * 2 + 1 ≤ end do (While the root has at least one child)
34 child := root * 2 + 1 (root*2 + 1 points to the left child)
35 swap := root (keeps track of child to swap with)
36 (check if root is smaller than left child)
37 if a[swap] < a[child]
38 swap := child
39 (check if right child exists, and if it's bigger than what we're currently swapping with)
40 if child < end and a[swap] < a[child+1]
41 swap := child + 1
42 (check if we need to swap at all)
43 if swap != root
44 swap(a[root], a[swap])
45 root := swap (repeat to continue sifting down the child now)
46 else
47 return
48
C++ 實(shí)現(xiàn)
1 // build one maximum heap
2 template <typename T>
3 void heapsort(std::vector<T>& a)
4 {
5 int sz = (int)a.size();
6 for (int i = sz/2; i >= 0; i--)
7 percDown(a, i, sz);
8 std::cout << "build heap is done.\n";
9 for (int j = sz-1; j > 0; j--) {
10 std::swap(a[0], a[j]);
11 percDown(a, 0, j);
12 }
13 }
14
15 inline int leftChild(int i)
16 {
17 return 2*i+1;
18 }
19
20 template <typename T>
21 void percDown(std::vector<T>& a, int i, int n)
22 {
23 int child;
24 T tmp;
25 for (tmp = a[i]; leftChild(i) < n; i = child) {
26 child = leftChild(i);
27 if (child != n-1 && a[child] < a[child+1])
28 child++;
29 if (tmp < a[child])
30 a[i] = a[child];
31 else
32 break;
33 }
34 a[i] = tmp;
35 }
36