[Algorithms] Heap and Heapsort

  1 #include <iostream>
  2 #include <vector>
  3 
  4 using namespace std;
  5 
  6 template<typename T> class Heap {
  7 public:
  8     Heap(vector<T>&);
  9     ~Heap(void);
 10     
 11     inline int parent(int);
 12     inline int left(int);
 13     inline int right(int);
 14 
 15     void max_heapify(int);
 16     void build_max_heap(void);
 17     void heap_sort(void);
 18 
 19     /* Methods for maximum priority queue. */
 20     T maximum(void);
 21     T extract_max(void);
 22     void increase_key(int, T);
 23     void insert_key(T);
 24 
 25     void print(void);
 26 private:
 27     vector<T> data;
 28     int heap_size;
 29 };
 30 
 31 template<typename T> Heap<T>::Heap(vector<T>& d) {
 32     data = d;
 33     build_max_heap();
 34 }
 35 
 36 template<typename T> Heap<T>::~Heap(void) {
 37     data.clear();
 38     heap_size = 0;
 39 }
 40 
 41 template<typename T> inline int Heap<T>::parent(int idx) {
 42     return (idx - 1) >> 1;
 43 }
 44 
 45 template<typename T> inline int Heap<T>::left(int idx) {
 46     return (idx << 1) + 1;
 47 }
 48 
 49 template<typename T> inline int Heap<T>::right(int idx) {
 50     return (idx << 1) + 2;
 51 }
 52 
 53 template<typename T> void Heap<T>::max_heapify(int idx) {
 54     int largest = idx;
 55     int l = left(idx);
 56     int r = right(idx);
 57     if (l < heap_size && data[l] > data[largest]) largest = l;
 58     if (r < heap_size && data[r] > data[largest]) largest = r;
 59     if (largest != idx) {
 60         swap(data[idx], data[largest]);
 61         max_heapify(largest);
 62     }
 63 }
 64 
 65 template<typename T> void Heap<T>::build_max_heap(void) {
 66     heap_size = data.size();
 67     for (int i = (heap_size >> 1) - 1; i >= 0; i--)
 68         max_heapify(i);
 69 }
 70 
 71 template<typename T> void Heap<T>::heap_sort(void) {
 72     int size = heap_size - 1;
 73     for (int i = size; i > 0; i--) {
 74         swap(data[i], data[0]);
 75         heap_size--;
 76         max_heapify(0);
 77     }
 78 }
 79 
 80 template<typename T> T Heap<T>::maximum(void) {
 81     return data[0];
 82 }
 83 
 84 template<typename T> T Heap<T>::extract_max(void) {
 85     if (data.empty()) throw runtime_error("Heap underflow!");
 86     int maximum = data[0];
 87     swap(data[0], data[heap_size - 1]);
 88     heap_size--;
 89     max_heapify(0);
 90     return maximum;
 91 }
 92 
 93 template<typename T> void Heap<T>::increase_key(int idx, T key) {
 94     if (key < data[idx]) {
 95         cerr << "New key is smaller!" << endl;
 96         return;
 97     }
 98     data[idx] = key;
 99     while (idx >= 0 && parent(idx) >= 0 && data[parent(idx)] < data[idx]) {
100         swap(data[idx], data[parent(idx)]);
101         idx = parent(idx);
102     }
103 }
104 
105 template<typename T> void Heap<T>::insert_key(T key) {
106     data.insert(data.begin() + heap_size, key - 1);
107     heap_size++;
108     increase_key(heap_size - 1, key);
109 }
110 
111 template<typename T> void Heap<T>::print(void) {
112     printf("In heap: ");
113     for (int i = 0; i < heap_size; i++)
114         printf("%d ", data[i]);
115     printf(", ");
116     if (heap_size < (int)data.size()) {
117         printf("Out of heap: ");
118         for (int i = heap_size; i < (int)data.size(); i++)
119             printf("%d ", data[i]);
120     }
121     printf("\n");
122 }
123 
124 void heap_test(void) {
125     int num[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
126     vector<int> nums(num, num + sizeof(num) / sizeof(int));
127     // Construct a heap and print it
128     Heap<int> heap(nums);
129     heap.print();
130     // Test maximum() and extract_max()
131     printf("%d\n", heap.maximum());
132     printf("%d\n", heap.extract_max());
133     heap.print();
134     // Test increase_key()
135     heap.increase_key(3, 5);
136     heap.print();
137     // Test insert_key()
138     heap.insert_key(20);
139     heap.print();
140     // Test heap_sort()
141     heap.heap_sort();
142     heap.print();
143 }
144 
145 int main(void) {
146     heap_test();
147     system("pause");
148     return 0;
149 }

In heap: 16 14 10 8 7 9 3 2 4 1 ,
16
16
In heap: 14 8 10 4 7 9 3 2 1 , Out of heap: 16
In heap: 14 8 10 5 7 9 3 2 1 , Out of heap: 16
In heap: 20 14 10 5 8 9 3 2 1 7 , Out of heap: 16
In heap: 1 , Out of heap: 2 3 5 7 8 9 10 14 20 16