# binaryheap.hpp

Go to the documentation of this file.

    00001 /* $Id: binaryheap.hpp 15296 2009-01-30 17:54:48Z smatz $ */
    00002
    00005 #ifndef  BINARYHEAP_HPP
    00006 #define  BINARYHEAP_HPP
    00007
    00026 template <class Titem_>
    00027 class CBinaryHeapT {
    00028 public:
    00029   typedef Titem_ *ItemPtr;
    00030 private:
    00031   int                     m_size;
    00032   int                     m_max_size;
    00033   ItemPtr                *m_items;
    00034
    00035 public:
    00036   explicit CBinaryHeapT(int max_items = 102400)
    00037     : m_size(0)
    00038     , m_max_size(max_items)
    00039   {
    00040     m_items = new ItemPtr[max_items + 1];
    00041   }
    00042
    00043   ~CBinaryHeapT()
    00044   {
    00045     Clear();
    00046     delete [] m_items;
    00047     m_items = NULL;
    00048   }
    00049
    00050 public:
    00053   FORCEINLINE int Size() const {return m_size;};
    00054
    00057   FORCEINLINE bool IsEmpty() const {return (m_size == 0);};
    00058
    00061   FORCEINLINE bool IsFull() const {return (m_size >= m_max_size);};
    00062
    00065   FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];}
    00066
    00069   bool Push(Titem_& new_item);
    00070
    00072   FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;};
    00073
    00075   void RemoveHead();
    00076
    00078   void RemoveByIdx(int idx);
    00079
    00081   int FindLinear(const Titem_& item) const;
    00082
    00085   void Clear() {m_size = 0;};
    00086
    00088   void CheckConsistency();
    00089 };
    00090
    00091
    00092 template <class Titem_>
    00093 FORCEINLINE bool CBinaryHeapT<Titem_>::Push(Titem_& new_item)
    00094 {
    00095   if (IsFull()) return false;
    00096
    00097   // make place for new item
    00098   int gap = ++m_size;
    00099   // Heapify up
    00100   for (int parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2)
    00101     m_items[gap] = m_items[parent];
    00102   m_items[gap] = &new_item;
    00103   CheckConsistency();
    00104   return true;
    00105 }
    00106
    00107 template <class Titem_>
    00108 FORCEINLINE void CBinaryHeapT<Titem_>::RemoveHead()
    00109 {
    00110   assert(!IsEmpty());
    00111
    00112   // at index 1 we have a gap now
    00113   int gap = 1;
    00114
    00115   // Heapify down:
    00116   //   last item becomes a candidate for the head. Call it new_item.
    00117   Titem_& new_item = *m_items[m_size--];
    00118
    00119   // now we must maintain relation between parent and its children:
    00120   //   parent <= any child
    00121   // from head down to the tail
    00122   int child  = 2; // first child is at [parent * 2]
    00123
    00124   // while children are valid
    00125   while (child <= m_size) {
    00126     // choose the smaller child
    00127     if (child < m_size && *m_items[child + 1] < *m_items[child])
    00128       child++;
    00129     // is it smaller than our parent?
    00130     if (!(*m_items[child] < new_item)) {
    00131       // the smaller child is still bigger or same as parent => we are done
    00132       break;
    00133     }
    00134     // if smaller child is smaller than parent, it will become new parent
    00135     m_items[gap] = m_items[child];
    00136     gap = child;
    00137     // where do we have our new children?
    00138     child = gap * 2;
    00139   }
    00140   // move last item to the proper place
    00141   if (m_size > 0) m_items[gap] = &new_item;
    00142   CheckConsistency();
    00143 }
    00144
    00145 template <class Titem_>
    00146 inline void CBinaryHeapT<Titem_>::RemoveByIdx(int idx)
    00147 {
    00148   // at position idx we have a gap now
    00149   int gap = idx;
    00150   Titem_& last = *m_items[m_size];
    00151   if (idx < m_size) {
    00152     assert(idx >= 1);
    00153     m_size--;
    00154     // and the candidate item for fixing this gap is our last item 'last'
    00155     // Move gap / last item up:
    00156     while (gap > 1)
    00157     {
    00158       // compare [gap] with its parent
    00159       int parent = gap / 2;
    00160       if (last < *m_items[parent]) {
    00161         m_items[gap] = m_items[parent];
    00162         gap = parent;
    00163       } else {
    00164         // we don't need to continue upstairs
    00165         break;
    00166       }
    00167     }
    00168
    00169     // Heapify (move gap) down:
    00170     while (true) {
    00171       // where we do have our children?
    00172       int child  = gap * 2; // first child is at [parent * 2]
    00173       if (child > m_size) break;
    00174       // choose the smaller child
    00175       if (child < m_size && *m_items[child + 1] < *m_items[child])
    00176         child++;
    00177       // is it smaller than our parent?
    00178       if (!(*m_items[child] < last)) {
    00179         // the smaller child is still bigger or same as parent => we are done
    00180         break;
    00181       }
    00182       // if smaller child is smaller than parent, it will become new parent
    00183       m_items[gap] = m_items[child];
    00184       gap = child;
    00185     }
    00186     // move parent to the proper place
    00187     if (m_size > 0) m_items[gap] = &last;
    00188   }
    00189   else {
    00190     assert(idx == m_size);
    00191     m_size--;
    00192   }
    00193   CheckConsistency();
    00194 }
    00195
    00196 template <class Titem_>
    00197 inline int CBinaryHeapT<Titem_>::FindLinear(const Titem_& item) const
    00198 {
    00199   if (IsEmpty()) return 0;
    00200   for (ItemPtr *ppI = m_items + 1, *ppLast = ppI + m_size; ppI <= ppLast; ppI++) {
    00201     if (*ppI == &item) {
    00202       return ppI - m_items;
    00203     }
    00204   }
    00205   return 0;
    00206 }
    00207
    00208 template <class Titem_>
    00209 FORCEINLINE void CBinaryHeapT<Titem_>::CheckConsistency()
    00210 {
    00211   // enable it if you suspect binary heap doesn't work well
    00212 #if 0
    00213   for (int child = 2; child <= m_size; child++) {
    00214     int parent = child / 2;
    00215     assert(!(m_items[child] < m_items[parent]));
    00216   }
    00217 #endif
    00218 }
    00219
    00220
    00221 #endif /* BINARYHEAP_HPP */