Sign in to follow this  
vs322

Understanding M.Buckland's IndexedPriorityQ

Recommended Posts

Feeling sort of dense right no, but I have gone over and over this templated class and really can't see how it works. I believe that it is supposed to sort item's index# by a key, but I really don't get it. I have implemented my own classes that do the same thing, so its not really a how to do it question, but more of a how did he do it question. (this is from the source code for "Programing Game AI by Example" and is totally glossed over in the book itself)
//----------------------- IndexedPriorityQLow ---------------------------
//
//  Priority queue based on an index into a set of keys. The queue is
//  maintained as a 2-way heap.
//
//  The priority in this implementation is the lowest valued key
//------------------------------------------------------------------------
template<class KeyType>
class IndexedPriorityQLow
{
private:

  std::vector<KeyType>&  m_vecKeys;

  std::vector<int>       m_Heap;
 
  std::vector<int>       m_invHeap;

  int                    m_iSize,
                         m_iMaxSize;

  void Swap(int a, int b)
  {
    int temp = m_Heap[a]; m_Heap[a] = m_Heap[b]; m_Heap[b] = temp;

    //change the handles too
    m_invHeap[m_Heap[a]] = a; m_invHeap[m_Heap[b]] = b;
  }

  void ReorderUpwards(int nd)
  {
    //move up the heap swapping the elements until the heap is ordered
    while ( (nd>1) && (m_vecKeys[m_Heap[nd/2]] > m_vecKeys[m_Heap[nd]]) )
    {      
      Swap(nd/2, nd);

      nd /= 2;
    }
  }

  void ReorderDownwards(int nd, int HeapSize)
  {
    //move down the heap from node nd swapping the elements until
    //the heap is reordered
    while (2*nd <= HeapSize)
    {
      int child = 2 * nd;

      //set child to smaller of nd's two children
      if ((child < HeapSize) && (m_vecKeys[m_Heap[child]] > m_vecKeys[m_Heap[child+1]]))
      {
        ++child;
      }

      //if this nd is larger than its child, swap
      if (m_vecKeys[m_Heap[nd]] > m_vecKeys[m_Heap[child]])
      {
        Swap(child, nd);

        //move the current node down the tree
        nd = child;
      }

      else
      {
        break;
      }
    }
  }


public:
  
  //you must pass the constructor a reference to the std::vector the PQ
  //will be indexing into and the maximum size of the queue.
  IndexedPriorityQLow(std::vector<KeyType>& keys,
                      int              MaxSize):m_vecKeys(keys),
                                                m_iMaxSize(MaxSize),
                                                m_iSize(0)
  {
    m_Heap.assign(MaxSize+1, 0);
    m_invHeap.assign(MaxSize+1, 0);
  }

  bool empty()const{return (m_iSize==0);}

  //to insert an item into the queue it gets added to the end of the heap
  //and then the heap is reordered from the bottom up.
  void insert(const int idx)
  {
    assert (m_iSize+1 <= m_iMaxSize);

    ++m_iSize;

    m_Heap[m_iSize] = idx;

    m_invHeap[idx] = m_iSize;

    ReorderUpwards(m_iSize);
  }

  //to get the min item the first element is exchanged with the lowest
  //in the heap and then the heap is reordered from the top down. 
  int Pop()
  {
    Swap(1, m_iSize);

    ReorderDownwards(1, m_iSize-1);

    return m_Heap[m_iSize--];
  }

  //if the value of one of the client key's changes then call this with 
  //the key's index to adjust the queue accordingly
  void ChangePriority(const int idx)
  {
    ReorderUpwards(m_invHeap[idx]);
  }
};


Any insight would be great.

Share this post


Link to post
Share on other sites
It's an implementation of a heap-base priority queue. A neat data structure which supports inserting random objects as well as removing the highest one in logarithmic time, and without any memory overhead. Clicky.

There's already a priority_queue adapter in STL, as well as separate heap functions. Though admittedly it's not a particularly hard algorithm to implement yourself when you've wrapped your head around it.

edit: Oops. Actually it seems to be a fancy heap version which tracks the current index of the inserted elements in order to support changing priorities efficiently.

The ChangePriority function also looks kind of weird. That is it only 'heapifies' upwards so presumably it can only increase the priority, right? As far as I can see a general ChangePriority and Remove functions should be efficient on this data structure.

[Edited by - implicit on September 17, 2008 10:41:09 AM]

Share this post


Link to post
Share on other sites
A heap is elementary data structure, a binary tree, where nodes respect certain properties. One of reasons heaps are desirable is due to their compact storage - n nodes can be stored in array of size n (hence making indexed access to any node trivial). Update and removal operations tend to efficient as well.

Any CS course covers how and why they work, so that's the best place to start looking. Example are abundant.

Share this post


Link to post
Share on other sites
I understand what a heap is, but I was more interested in how the class in the code worked. I too only see how it can resort something upward. I seems to be a very specific use piece of code. And not a "classic" Priority queue.

Share this post


Link to post
Share on other sites
Quote:
Original post by vs322
I understand what a heap is, but I was more interested in how the class in the code worked. I too only see how it can resort something upward. I seems to be a very specific use piece of code. And not a "classic" Priority queue.
There's not much to it as far as I can tell.
In addition to the normal heap structure there's an extra array which keeps track of the index within the heap of each item (m_invHeap). This is equivalent to keeping a pointer within the object structure to its corresponding heap slot, and updating it whenever it is inserted or moved (e.g. swapped).
Furthermore there's a level of indirection, provided by indices rather than pointers, used to avoid moving the actual objects around. This is what the heap array itself stores.

Aside from that the code looks like a traditional heap implementation. The design looks more then a little odd for use a generic container, but then it's appears to be tailored for one specific application.
I suppose you could speed things up a bit though. By embedding an objects inverse index within the objects themselves to get more mileage out of the cache, by adding a sentinel node at the top (and possibly at the bottom) of the heap, or by using right shifts rather than division by two, etc.

To 'fix' the ChangePriority function I believe you can simply check whether the priority has increased or decreased and call the upheap or the downheap function respectively.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this