data structure

data structure | heap

  1 #include <iostream>
  2 #include <string.h>
  3 using namespace std;
  4 
  5 template <class T>
  6 class Heap {
  7 public:
  8     Heap():n(0), capacity(100) {
  9         this->arr = new T[capacity];
 10     }
 11 
 12     ~Heap() {
 13         delete[] arr;
 14     }
 15 
 16     void insert(T v) {
 17         if (n >= capacity) {
 18             T* tmp = new T[capacity << 1];
 19             memcpy(tmp, arr, sizeof(T) * capacity);
 20             capacity <<= 1;
 21         }
 22         arr[n++] = v;
 23         shiftUp(n - 1);
 24     }
 25 
 26     void del(int index) {
 27         if (index < 0 || index >= n) return;
 28         swap(arr[index], arr[n - 1]);
 29         shiftDown(index, --n);
 30     }
 31 
 32     void shiftDown(int st, int ed) {
 33         T tmp = arr[st];
 34         while (st < ed) {
 35             int next = -1;
 36             int left = st * 2 + 1; // left child node 
 37             if (left < ed) next = left;
 38             else break;
 39             int right = st * 2 + 2;
 40             if (right < ed && arr[right] < arr[next]) next = right;
 41             if (arr[next] < arr[st]) {
 42                 arr[st] = arr[next];
 43                 st = next;
 44             } else break;
 45         }
 46         arr[st] = tmp;
 47     }
 48 
 49     void shiftUp(int ed) {
 50         T tmp = arr[ed];
 51         while (ed > 0) {
 52             int parent = (ed - 1) / 2;
 53             if (arr[ed] < arr[parent]) {
 54                 arr[ed] = arr[parent];
 55                 ed = parent;
 56             } else break;
 57         }
 58         arr[ed] = tmp;
 59     }
 60 
 61     void sort() {
 62         for (int j = n - 1; j >= 1; --j) {
 63             swap(arr[0], arr[j]);
 64             shiftDown(0, j); // here should be j
 65         }
 66     }
 67 
 68     void print() const {
 69         for (int i = 0; i < n; ++i) {
 70             cout << arr[i] << " ";
 71         }
 72         cout << endl;
 73     }
 74 
 75     T get(int pos) {
 76         return arr[pos];
 77     }
 78 
 79     void update(int pos, int v) {
 80         if (pos < 0 || pos >= n) return;
 81         if (arr[pos] < v) {
 82             arr[pos] = v;
 83             shiftDown(pos, n);
 84         } else {
 85             shiftUp(pos);
 86         }
 87     }
 88     void increase(int pos, int v) {
 89         if (pos < 0 || pos >= n) return;
 90         arr[pos] = arr[pos] + v;
 91         shiftDown(pos, n);
 92     }
 93 
 94     void decrease(int pos, int v) {
 95         if (pos < 0 || pos >= n) return;
 96         arr[pos] = arr[pos] - v;
 97         shiftUp(pos);
 98     }
 99 
100     bool empty() const {
101         return n <= 0;
102     }
103 
104     void pop() {
105         if (empty()) return;
106         del(0);
107     }
108 
109     T top() {
110         if (empty()) return;
111         return arr[0];
112     }
113 
114 private:
115     T* arr;
116     int n;
117     int capacity;
118 };
119 
120 int main()
121 {
122     int arr[] = {1, 10,2,4,8,7};
123     Heap<int> heap;
124     for (int i = 0; i < 6; ++i) {
125         heap.insert(arr[i]);
126     }
127     //heap.sort();
128     heap.print();
129     heap.del(3);
130     heap.print();
131     heap.increase(1, 10);
132     heap.print();
133     return 0;
134 }