Implement Heap

来源：Bloomberg onsite

原帖：

题目：
Implement a heap structure.

代码：

 #include <vector>  
 #include <iostream>  
 using namespace std;  

 typedef int heap_element;
 /* 堆，默认为最小堆 */  
 int cmp_int(const heap_element& x, const heap_element& y) {  
      heap_element dif = x - y;  
      if (dif > 0) {  
           return 1;  
      } else if (dif < 0) {  
           return -1;  
      } else {  
           return 0;  
      }  
 }  
 typedef int (*compare)(const heap_element& x, const heap_element& y);  
 class heap {  
 public:  
      heap(compare _cmp) {  
           cmp = _cmp;  
      }  
      bool empty() const {  
           return element.size() == 0;   
      }  
      int size() const {  
           return element.size();  
      }  
      void push(const heap_element x) {  
           element.push_back(x);  
           heap_sift_up(element.size() - 1);  
      }  
      void pop() {  
           if (element.size() <= 0) {  
                cerr << "heap is out of space" << endl;  
           }  
           swap(element[0], element[element.size() - 1]);  
           element.pop_back();  
           if (element.size() == 0) {  
                return;  
           }  
           heap_sift_down(0);  
      }  
      heap_element top() const {  
           return element[0];  
      }  
 private:  
      void heap_sift_down(int start) {  
           int i = start, j = 2 * i + 1;  
           while (j < element.size()) {  
                if (j < element.size() - 1 && cmp(element[j], element[j+1]) > 0) {  
                     j++;  
                }  
                if (cmp(element[i], element[j]) < 0) {  
                     break;                      
                } else {  
                     swap(element[i], element[j]);  
                }  
                i = j;  
                j = 2 * i + 1;  
           }  
      }  
      void heap_sift_up(int start) {  
           int j = start, i = (j - 1) / 2;  
           while (j >= 0) {  
                if (cmp(element[i], element[j]) <= 0) {  
                     break;  
                } else {  
                     swap(element[i], element[j]);  
                }  
                j = i;  
                i = (j - 1) / 2;  
           }  
      }  
      vector<heap_element> element;  
      compare cmp;  
 };  
 int main() {  
      int myints[] = {10,20,30,5,15};  
       vector<int> v(myints,myints+sizeof(myints)/sizeof(int));  
       heap minheap(cmp_int);  
       for(int i = 0; i < v.size(); ++i) {  
            minheap.push(v[i]);  
       }  
       cout << minheap.top() << endl;  
       // const vector<int>& elements = minheap.getElements();   
       // for (auto& i : elements) {  
       //      cout << i << " ";  
       // }  
       // cout << endl;  
 }