/** 
  * Updates the priority associated with a item in the queue. This
  * function fails if the item is not already present.
 */
 void update(T item, Priority priority) {
   // Verify that the item is currently in the queue
   typename index_map_type::const_iterator iter = index_map.find(item);
   assert(iter != index_map.end());
   // If it is already present update the priority
   size_t i = iter->second;
   heap[i].second = priority;
   while ((i > 1) && (priority_at(parent(i)) < priority)) {
     swap(i, parent(i));
     i = parent(i);
   }
   heapify(i);
 }

 //! Remove an item from the queue
 bool remove(T item) {
   // Ensure that the element is in the queue
   typename index_map_type::iterator iter = index_map.find(item);
   // only if the element is present in the first place do we need
   // remove it
   if(iter != index_map.end()) {
     size_t i = iter->second;
     swap(i, size());
     heap.pop_back();
     heapify(i);
     // erase the element from the index map
     index_map.erase(iter);
     return true;
   } 
   return false;
 }

 /**
  * If item is already in the queue, sets its priority to the sum
  * of the old priority and the new one. If the item is not in the queue,
  * adds it to the queue.
  *
  * returns true if the item was already present
  */
 bool insert_cumulative(T item, Priority priority) {
   // determine if the item is already in the queue
   typename index_map_type::const_iterator iter = index_map.find(item);
   if(iter != index_map.end()) { // already present
     // If it is already present update the priority
     size_t i = iter->second;
     heap[i].second = priority + heap[i].second;
     // If the priority went up move the priority until its greater
     // than its parent
     while ((i > 1) && (priority_at(parent(i)) <= priority)) {
       swap(i, parent(i));
       i = parent(i);
     } 
     // Trickle down if necessary
     heapify(i);  // This should not be necessary
     return false;
   } else { // not already present so simply add
     push(item, priority);
     return true;
   }
 } // end of insert cumulative

 vector_property_map(unsigned inital_size, 
                     const index_map_type& index = index_map_type())
   : inherited(index.process_group(), index.global(),
               local_iterator_map(inital_size, index.base())) { }

 //! Returns the weight associated with a key
 Priority get(T item) const {
   typename index_map_type::const_iterator iter = index_map.find(item);
   assert(iter != index_map.end());
   size_t i = iter->second;
   return heap[i].second;
 }

 iterator_property_map(RandomAccessIterator cc, const index_map_type& id)
   : inherited(id.process_group(), id.global(), 
               local_iterator_map(cc, id.base())) { }

two_bit_color_map(std::size_t inital_size, 
                  const index_map_type& index = index_map_type())
  : inherited(index.process_group(),  index.global(),
              local_map(inital_size, index.base())) { }

 /**
  * Removes the item with maximum priority from the queue, and
  * returns it with its priority.
  */
 std::pair<T, Priority> pop() {
   assert(!empty());
   heap_element top = heap[1];
   swap(1, size());
   heap.pop_back();
   heapify(1);
   index_map.erase(top.first);
   return top;
 }

 //! Clears all the values (equivalent to stl clear)
 void clear() {
   heap.clear();
   heap.push_back(std::make_pair(T(), Priority()));
   index_map.clear();
 }

 //! Returns true if the queue contains the given value
 bool contains(const T& item) const {
   return index_map.count(item) > 0;
 }