// MaxHeap.h
/* MaxHeap: binary tree of which data of any node >= either its child */ /* Using a dynamic array to store nodes, while i stands for a parent node, 2i and 2i + 1 are its children */
template<class T> class MaxHeap { public: MaxHeap (int maxHeapSize = 10); /* heap points to array a when initializing, for preventing to delete the array a when calling ~MaxHeap (), make heap point nothing */ ~MaxHeap () { heap = 0; delete [] heap;} int size () const { return currentSize;} T max () {if (currentSize == 0) throw OutOfBounds (); return heap[1];} MaxHeap<T>& insert (const T x); MaxHeap<T>& sift (); void initialize (T a[], int arraySize); private: int currentSize, maxSize; T *heap; };
// implementation should be included in declaring file
template<class T> MaxHeap<T>::MaxHeap (int maxHeapSize) { maxSize = maxHeapSize; heap = new T[maxSize + 1]; // heap[1] as begining currentSize = 0; }
/* insert a new node with the valude of x */ template<class T> MaxHeap<T>& MaxHeap<T>::insert (const T x) { int i; if (currentSize == maxSize) //throw NoMem(); printf ("no memory!/n"); else { // looking for the position of the new node from the new node // bottom-up i = ++currentSize; while (i != 1 && x > heap[i / 2]) { heap[i] = heap[i / 2]; // exchange the position of the new node and its parent i /= 2; // up } heap[i] = x; } return *this; }
/* exchange the root and the last node, minish the currentSize by 1 and adjust the structure of the whole tree */ template<class T> MaxHeap<T>& MaxHeap<T>::sift () { if (currentSize != 0) //throw OutOfBounds (); { T y = heap[currentSize]; // the last node
// allocate heap[1] (the max node) to the previous y position // then minish currentSize by 1 heap[currentSize--] = heap[1]; // looking for y's position from the root // top-down int i = 1, j = 2; // initialize i as the root, and j as left child while (j <= currentSize) { // select the bigger child of the node if (j < currentSize && heap[j + 1] > heap[j]) j++; if (y < heap[j]) { heap[i] = heap[j]; // exchange the position of parent and child i = j; // down j *= 2; } else break; } heap[i] = y; // the new position of y } return *this; }
template<class T> void MaxHeap<T>::initialize (T a[], int arraySize) { delete [] heap; heap = a; currentSize = 1; // a[1] as root maxSize = arraySize - 1; // a[0] doesn't count
// in the beginning, a[1] as root, then insert the rest of array a one by one for (int i = 2; i < arraySize; i++) insert (a[i]); }
// heapSort.cpp
//#include "MaxHeap.h" #include <iostream> using namespace std;
template<class T> /* sorting a[1 : arraySize - 1] */ void heapSort (T a[], int arraySize) { MaxHeap<T> H(1); H.initialize (a, arraySize); // a[0] doesn't count for (int i = 1; i < arraySize; i++) H.sift (); }
int main () { int a[10] = {0,6,8,9,4,1,3,7,2,5}; heapSort<int> (a, 10); for (int i = 1; i < 10; i++) cout << a[i] << " "; cin.get(); return 0; }
