Transcript Heaps and priority queues

Week 10:
Heap and Priority queue
Any feature here?
Heap
• No particular relationship among nodes on any
given level, even among the siblings
• When a heap is a complete binary tree, it has a
smallest possible height—a heap with N nodes
always has O(log N) height.
• A heap is a useful data structure when you need
to remove the object with the highest (or
lowest) priority.
Heaps
• For a maximum heap, the value of a parent is greater than or
equal to the value of each of its children.
• For a minimum heap, the value of the parent is less than or
equal to the value of each of its children.
• We assume that a heap is a maximum heap.
Vectors and complete binary trees
• In practice, heaps are usually implemented as arrays
• A complete binary tree of depth d contains all possible nodes through
level d - 1 and that nodes at level d occupy the leftmost positions in the
tree.
How to figure out parent-child from
indices?
Heap = Array-based trees
• With some simple rules, we can view a direct-access
container, such as an array or vector, as a binary tree.
• These trees are referred to as array-based trees and
form the basis for a new container type, called a heap
• Heaps are designed to provide efficient access to the
maximum element or the minimum element in the
collection.
• In this way, a heap acts like a priority queue. The
highest (or lowest) priority element is always stored at
the root, hence the name heap.
Heapify
• Heapify() maintain the heap property
• Given: a node i in the heap with children l and r (two
subtrees rooted at l and r )
• Problem: The subtree rooted at i violate the heap
property
• Action: let the value of the parent node recursively
“float down” so subtree rooted a i satisfy the heap
property
Analyzing Heapify()
• When Heapify is called, the running time depends on how far
an element might move down in tree. In other words it
depends on the height h (depth d) of node. In the worst case
the element might go down all the way to the leaf level, which
is O(logN).
Heapify all subtrees in a tree
• Wiki – Building a heap:
Insertion
• A heap is an array-based tree with a vector as the
underlying storage structure.
• What makes the tree a heap is the ordering of the
elements.
1. push_back -- O(1)
2. Re-heapify -- O(logN)
Deletion
• Deletion from a heap is restricted to the root only. Hence,
the operation specifically removes the largest element.
1. Exchange -- O(1)
2. pop_back -- O(1)
3. Re-heapify -- O(logN)
Time complexity - Heap
• Find max/min: O(1)
• Delete max/min: O(logN)
• Insert max/min: O(logN)
A heap is a useful data structure when you need to
remove the object with the highest (or lowest) priority.
Still remember the Priority Queue?
• We discussed in week 5 on “Queues”
Priority Queue
A Special form of queue from which items are removed
according to their designated priority and not the order
in which they entered.
Job # 1
Manager
Job # 4
Supervisor
Job # 3
Clerk
Job # 2
President
Items entered the queue in sequential order but will be
removed in the order #2, #1, #4, #3.
26
Main Index
Contents
Heaps and priority queues
• Heap delete() operation removes the optimal element
from the heap, much like Priority-queue pop()
operation remove the highest priority element from
priority queue.
• Heap insertion() simply adds an element, much like
the Priority-queue push() operation.
• Both the heap insertion and deletion operations
update the underlying tree storage structure in such a
way that it remains a heap; that is, they maintain the
integrity of the storage structure.
Heaps and priority queues
• The standard container adaptor priority_queue
calls make_heap, push_heap and pop_heap automatically to
maintain heap properties for a container.
Priority queue
Heap
The storage structure should be selected so that
the container operations can be implemented
efficiently
29
Reading
• Chapter 6
Reminder:
HW4 Due Wednesday 11/5/2014
Submission before Thursday
10/30/2014 will receive 30 extra points