next up previous contents
Next: BinomialHeap Up: Priority Queue Dictionary Structures Previous: Priority Queue Dictionary Structures

BinaryHeap

Priority queues are data structures which support fast insertion and extract-minimum operations. They are templated on both key and information fields, with the key field defining where the information sits in the heap.
  
Figure 2.13: BinaryHeap
\begin{figure}
\begin{flushleft}
\begin{minipage}[t]
{\textwidth}
\hrulefill

\v...
 ...nd{verbatim}
\vspace*{-6mm}

\hrulefill\end{minipage}\end{flushleft}\end{figure}


  
Figure 2.14: Another BinaryHeap example
\begin{figure}
\begin{flushleft}
\begin{minipage}[t]
{\textwidth}
\hrulefill

\v...
 ...nd{verbatim}
\vspace*{-6mm}

\hrulefill\end{minipage}\end{flushleft}\end{figure}

1. Creation






 
Figure 2.14: Another BinaryHeap example
BinaryHeap<Key,Item> bh;



Create a binary heap of size BINHEAPSIZE (defined in general.h), with an array-based implementation. This is a fast priority queue if the number of elements is predetermined and unions are infrequent.









BinaryHeap<Key,Item> binary_heap_name( (int) n);



Create a binary heap of size n.







2. Operations






BinaryHeapNode<Key,Item>* insert (Key k, Item i)



Insert item i with key k into the heap, returning a pointer to the node containing it. $O(\log n)$









void remove (Item i)



This does nothing. It is defined with an empty body to provide a definition for the Container::remove(Item) method.









Item extractMin ()



Removes the node with minimum key from the heap and returns the information stored within. $O(\log n)$









Item get ()



Calls extractMin(). $O(\log n)$









BinaryHeapNode<Key,Item>* minimum ()



Return a pointer to the node containing the minimum item in the heap, but do not remove it. O(1)









Item min ()



Call minimum(), then extract the Item from the returned node. O(1)









int size ()



Return the number of items stored in the heap. An element count is always stored. O(1)









Bool emptyQ ()



Is the heap empty? O(1)









Bool fullQ ()



Is the heap full? O(1)









Bool memberQ (const Item&)



Is the item in the heap? O(n)









Bool sortedQ () const



Return FALSE. O(1).









void clear ()



Remove all the elements from the priority queue. O(n)









void decreaseKey (BinaryHeapNode<Key,Item>* node, Item k)



Decreases the value of the key in node to the new key value k. $O(\log n)$









void deleteKey (ContainerNode* node)



Remove the entry in noda from the heap. $O(\log n)$









ostream& display (ostream&)



Produce a human-readable display of the data structure. O(n)









friend ostream& operator<< (ostream& s, Heap<Item>& h)



Output h to output stream s. This is the inverse operation of >>.









ObjectType type ()



What type/implementation of priority queue is this?








next up previous contents
Next: BinomialHeap Up: Priority Queue Dictionary Structures Previous: Priority Queue Dictionary Structures
RHS Linux User
1/26/1998