00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef BasicHeap_h
00021 #define BasicHeap_h
00022
00023 #include "Vec.h"
00024
00025
00026
00027
00028
00029 template<class Comp>
00030 class BasicHeap {
00031 Comp lt;
00032 vec<int> heap;
00033
00034
00035 static inline int left (int i) { return i*2+1; }
00036 static inline int right (int i) { return (i+1)*2; }
00037 static inline int parent(int i) { return (i-1) >> 1; }
00038
00039 inline void percolateUp(int i)
00040 {
00041 int x = heap[i];
00042 while (i != 0 && lt(x, heap[parent(i)])){
00043 heap[i] = heap[parent(i)];
00044 i = parent(i);
00045 }
00046 heap [i] = x;
00047 }
00048
00049
00050 inline void percolateDown(int i)
00051 {
00052 int x = heap[i];
00053 while (left(i) < heap.size()){
00054 int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i);
00055 if (!lt(heap[child], x)) break;
00056 heap[i] = heap[child];
00057 i = child;
00058 }
00059 heap[i] = x;
00060 }
00061
00062
00063 bool heapProperty(int i) {
00064 return i >= heap.size()
00065 || ((i == 0 || !lt(heap[i], heap[parent(i)])) && heapProperty(left(i)) && heapProperty(right(i))); }
00066
00067
00068 public:
00069 BasicHeap(const C& c) : comp(c) { }
00070
00071 int size () const { return heap.size(); }
00072 bool empty () const { return heap.size() == 0; }
00073 int operator[](int index) const { return heap[index+1]; }
00074 void clear (bool dealloc = false) { heap.clear(dealloc); }
00075 void insert (int n) { heap.push(n); percolateUp(heap.size()-1); }
00076
00077
00078 int removeMin() {
00079 int r = heap[0];
00080 heap[0] = heap.last();
00081 heap.pop();
00082 if (heap.size() > 1) percolateDown(0);
00083 return r;
00084 }
00085
00086
00087
00088 bool heapProperty() {
00089 return heapProperty(1); }
00090
00091
00092
00093 int getmin () { return removeMin(); }
00094 };
00095
00096
00097
00098 #endif