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 }