Priority Queue (Using Heap)
- frmpriorityqueue.ui
- ui_frmpriorityqueue.h
- frmpriorityqueue.h
- frmpriorityqueue.cpp
- heap.h
- heap.cpp
Priority Queue is an implementation of a Heap Structure which use a binary balanced tree, using a array. This sample get the item with the lesser key value.
This sample use a graph to show the binary balanced tree and use the methods that the structure Heap provides:
- Insert: Insert a new item into the heap. The heap will order the item using the operation Heapify Up or Heapify Down.
- FindMin. Gets the first element of the queue, the item with less key value. this operation doesn't take out the item from the queue.
- ExtractMin. Takes out the first element of the queue, the item with less key value. This operation will fix the tree with Heapify Down.
- Delete. Delete an item in from a specific position. This operation will fix the tree with an Heapify Down or Heapify Up.
- heapify_up. Fix the tree from an specific position to upper, until to root node.
- heapify_down. Fix the tree from an specific position to down, until to find a leaf node.
The class Heap use a class called HeapItem which must be inherited in the class that will be the final item of the Heap. This class HeapItem has the basic property Key which the heap structure require to implement the algorithm of sort and contains the position in the heap and id of its parent.
