+ //! get the index of the parent of the node at i.
+ /*! this will not return the parent index of the root, since there is no parent. */
+ int parent_index(int i)
+ {
+ return i / 2; // rely on integer division to shave off remainder.
+ }
+
+ //! returns the left child of node at position i.
+ int left_child(int i)
+ {
+ return 2 * i + 1;
+ }
+
+ //! returns the right child of node at position i.
+ int right_child(int i)
+ {
+ return 2 * i + 2;
+ }
+
+ //! re-sorts the heapspace to maintain the heap ordering.
+ void heapify()
+ {
+ int start = parent_index(_total - 1);
+ // iterate from the back of the array towards the front, so depth-first.
+ while (start >= 0) {
+ // sift down the node at the index 'start' such that all nodes below it are heapified.
+ sift_down(start, _total - 1);
+ start--; // move the start upwards towards the root.
+ }
+ }
+
+ void sift_down(int start, int end)
+ {
+ int root = start;
+
+ // while the current root still has a kid...
+ while (left_child(root) <= end) {
+ int child = left_child(root);
+ // figure out which child to swap with.
+ int swap = root;
+ // check if the root should be swapped with this kid.
+ if ((!_reverse && (_heapspace[swap] > _heapspace[child]))
+ || (_reverse && (_heapspace[swap] < _heapspace[child])))
+ {
+ swap = child;
+ }
+ // check if the other child should be swapped with the root or left kid.
+ if ((child + 1 <= end)
+ && ((!_reverse && (_heapspace[swap] > _heapspace[child + 1]))
+ || (_reverse && (_heapspace[swap] < _heapspace[child + 1]))))
+ {
+ swap = child + 1;
+ }
+ if (swap == root) {
+ // the root has the largest (or smallest) element, so we're done.
+ return;
+ } else {
+ swap_values(root, swap);
+ root = swap;
+ // repeat to continue sifting down the child now.
+ }
+ }
+ }
+
+ //! re-sorts the heapspace to maintain the heap ordering. this uses sift_up.
+ void alt_heapify()
+ {
+ int end = 1; // start at first child.
+
+ while (end < _total) {
+ // sift down the node at the index 'start' such that all nodes below it are heapified.
+ sift_up(0, end++);
+ }
+ }
+
+ //! start is how far up in the heap to sort. end is the node to sift.
+ void sift_up(int start, int end)
+ {
+ int child = end;
+ // loop until we hit the starting node, where we're done.
+ while (child > start) {
+ int parent = parent_index(child);
+ if ((!_reverse && (_heapspace[parent] < _heapspace[child]))
+ || (_reverse && (_heapspace[parent] > _heapspace[child])))
+ {
+ swap_values(parent, child);
+ child = parent;
+ // continue sifting at the parent now.
+ } else {
+ // done sorting.
+ return;
+ }
+ }
+ }
+
+ private:
+ bool _reverse; // is the sorting in reverse?
+ int _total; // how many total elements are there?
+ int *_heapspace; // track a pointer to the array.
+ };
+
+ /*!
+ * heap sort
+ *
+ * operates in O(n log(n)).
+ * sorts the original array.
+ */
+ template<class type>
+ void heap_sort(type v[], int n, bool reverse = false)
+ {
+ // reverse the sense of "reverse", since our algorithm expects a normal heap (with largest on top).
+ heap<type> hap(v, n, !reverse);
+
+ int end = n - 1;
+ while (end > 0) {
+ // a[0] is the root and largest value for a normal heap. The swap moves it to the real end of the list and takes it out of consideration.
+ hap.swap_values(end, 0);
+ // reduce the heap size by 1.
+ end--;
+ // that swap ruined the heap property, so re-heapify.
+ hap.sift_down(0, end);
+ }