C:/knet/include/kNet/MaxHeap.h

Go to the documentation of this file.

/* Copyright 2010 Jukka Jylänki

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License. */
#pragma once

#include "Array.h"
#include "SortCmp.h"

namespace kNet
{

template<typename T>
class EmptyLookupNotify
{
public:
   void IndexUpdated(const T &element, int newIndex) {}
};

template<typename T, typename PriorityCmp = sort::TriCmpObj<T>,
         typename EqualCmp = sort::TriCmpObj<T>, 
         typename LookupNotify = EmptyLookupNotify<T>,
         typename AllocT = StdCAlloc>
class MaxHeap
{
public:
   Array<T, AllocT> data;
   PriorityCmp cmp; // The object to use in comparing the priorities of the elements.
   EqualCmp equal; // The object to use in comparing the equality of the elements.
   
   // This object is invoked whenever objects are moved around in the heap. The LookupNotify object
   // can be used to give O(1) membership search. Useful when IncreaseKey needs to be used.
   LookupNotify notify; 

   static inline int ParentIndex(int i) { return (i+1)/2-1; }
   static inline int LeftChildIndex(int i) { return i*2+1; }
   static inline int RightChildIndex(int i) { return i*2+2; }

   bool MaxHeapify(int i);

   void KeyIncreased(int i);

   void Insert(const T &value);

   void PopFront();

   void PopBack();

   const T &Front() const { return data[0]; }

   const T &Back() const { return data[LowestPriorityIndex()]; }

   int LowestPriorityIndex() const;

   int Size() const { return data.size(); }

   void Reserve(int size) { data.reserve(size); }

   void Clear() { data.clear(); }
   int Search(const T &value) { return Search(value, 0); }

private:
   int Search(const T &value, int index);

};

template<typename T, typename PriorityCmp, typename EqualCmp, typename LookupNotify, typename AllocT>
bool MaxHeap<T, PriorityCmp, EqualCmp, LookupNotify, AllocT>::MaxHeapify(int i)
{
   assert(i >= 0);
   if (i >= (int)data.size())
      return false;

   bool changes = false;

   for(;;) // Eventually we will run out of children or no swap will occur.
   {
      // Get the indices to both children. Note that these might point to >= heapSize if a child is not present.
      const int l = LeftChildIndex(i);
      const int r = RightChildIndex(i);

      // Determine the largest node
      int largest = i;
      if (l < (int)data.size() && cmp(data[l], data[i]) > 0)
         largest = l;
      if (r < (int)data.size() && cmp(data[r], data[largest]) > 0)
         largest = r;

      // If i is not the largest node, switch and continue to MaxHeapify the child node.
      if (largest != i)
      {
         std::swap(data[largest], data[i]);
         notify.IndexUpdated(data[largest], largest);
         notify.IndexUpdated(data[i], i);
         i = largest;
         changes = true;
      }
      else
         return changes; // Return whether changes were made to heap.
   }
}

template<typename T, typename PriorityCmp, typename EqualCmp, typename LookupNotify, typename AllocT>
void MaxHeap<T, PriorityCmp, EqualCmp, LookupNotify, AllocT>::Insert(const T &value)
{
   // New element is added to the end of the array.
   data.push_back(value);
   notify.IndexUpdated(data.back(), data.size()-1);
   // We need to fix the heap by MaxHeapifying all the way to the top.
   KeyIncreased(data.size()-1);
}

template<typename T, typename PriorityCmp, typename EqualCmp, typename LookupNotify, typename AllocT>
void MaxHeap<T, PriorityCmp, EqualCmp, LookupNotify, AllocT>::KeyIncreased(int i)
{
   // We need to fix the heap by MaxHeapifying all the way to the top.
   bool changesMade = true;
   while(changesMade && i != 0)
   {
      i = ParentIndex(i);
      changesMade = MaxHeapify(i);
   }
}

template<typename T, typename PriorityCmp, typename EqualCmp, typename LookupNotify, typename AllocT>
void MaxHeap<T, PriorityCmp, EqualCmp, LookupNotify, AllocT>::PopFront()
{
   std::swap(data[0], data[data.size()-1]);
   data.pop_back();
   MaxHeapify(0);
}

template<typename T, typename PriorityCmp, typename EqualCmp, typename LookupNotify, typename AllocT>
void MaxHeap<T, PriorityCmp, EqualCmp, LookupNotify, AllocT>::PopBack()
{
   int i = LowestPriorityIndex();
   std::swap(data[i], data[data.size()-1]);
   data.pop_back();
   KeyIncreased(i);
}

template<typename T, typename PriorityCmp, typename EqualCmp, typename LookupNotify, typename AllocT>
int MaxHeap<T, PriorityCmp, EqualCmp, LookupNotify, AllocT>::LowestPriorityIndex() const
{
   int i = data.size();
   int lowestIndex = data.size()-1;
   do
   {
      --i;
      if (cmp(data[i], data[lowestIndex]) < 0)
         lowestIndex = i;
   } while((i & (i-1)) != 0);

   return lowestIndex;
}

template<typename T, typename PriorityCmp, typename EqualCmp, typename LookupNotify, typename AllocT>
int MaxHeap<T, PriorityCmp, EqualCmp, LookupNotify, AllocT>::Search(const T &value, int index)
{
   assert(index >= 0);
   if (index >= (int)data.size())
      return -1;

   int order = cmp(value, data[index]);
   if (order == 0 && equal(value, data[index]) == 0)
      return index;
   if (order > 0) // The element at data[index] < value, and all the children are also smaller, so
      return -1;  // there is no chance of finding the element.

   // case order < 0:
   int child = LeftChildIndex(index);
   assert(child >= 0);
   if (child >= (int)data.size()) // No left child, so no right child either, return not found.
      return -1;

   int result = Search(value, child);
   if (result != -1) // found on the left branch?
      return result;

   child = RightChildIndex(index);
   assert(child >= 0);
   if (child < (int)data.size()) // If right child exists, search there too.
      return Search(value, child);
   else
      return -1;
}

} // ~kNet