Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:garrett:entries:week_2 [2012/01/25 04:59] – 2.4: time characterizations garrettheath4
+++ courses:cs211:winter2012:journals:garrett:entries:week_2 [2012/03/07 03:45] (current) – enabled discussion garrettheath4
@@ Line 26: / Line 26: @@
 === Priority Queues ===
-**Priority queues** are useful data structures to use for ensuring that elements of a set are always sorted and considered in order from greatest priority to least priority.  A data structure that can be used to implement a priority queue is a heap.  A **heap** is a balanced binary tree in which every element's children are larger than itself.
+**Priority queues** are useful data structures to use for ensuring that elements of a set are always sorted and considered in order from greatest priority to least priority.  A data structure that can be used to implement a priority queue is a heap.  A **heap** is a balanced binary tree in which every element's children are larger than itself.  If we use a heap to implement a priority queue, then we must take into account what should happen when an element is added or removed from the heap.  If an element is removed from the heap, the last element in the heap is swapped into the deleted node and the ''Heapify-down'' algorithm is performed on that node.  Similarly, if an element is added to the heap, it is added as the last element of the heap and the ''Heapify-up'' algorithm is performed on it.
 ~~DISCUSSION~~