Transcript Heaps - Classes

CS 261 – Data Structures
Priority Queues & Heaps
Priority Queues
• Not really a FIFO queue – misnomer!!
• Associates a “priority” with each object:
– First element has the highest priority
• A data structure that supports the PQueue interface:
public void add(Object val);
public Object getFirst();
public void removeFirst();
• Examples of priority queues:
– To do list with priorities
– Active processes in an OS
Use of Priority Queues in Simulations
• The original, and one of the most important uses of
Priority queues
• Discrete Event Driven Simulation
• Actions are represented by “events” - things that have (or
will) happen at a given time
• The PQ maintains list of pending events. Highest priority
is next event.
• Event is pulled from list, executed, usually spawns more
events, which are then inserted into the PQ.
• Loop until everything happens, or until fixed time is
reached.
Priority Queue Applications
• Discrete event-driven simulation – i.e., a simulation of a
process where events occur
• Example: Ice cream store
– People arrive
– People order
– People leave
• Simulation Algorithm:
1. Determine the times of each event using a random number
generator with some distribution:
2. Put all events in a priority queue based on when it happens
3. Simulation framework pulls the minimum (next to happen) and
executes the event
Priority Queue Applications
• Many types of events … but they all have a time when
they occur
• Can we store various types of events in a priority queue?
– Heterogeneous collection
– Keep a pointer to action, or a flag to tell what action to perform
– So, have your comparison based on the time
Priority Queues: Implementations
add
getFirst
removeFirst
SortedArray
SortedList
LinkedList
O(n)
O(n)
O(1)
Binary search
Slide data up
Linear search
addLast(obj)
O(1)
O(1)
O(n)
elementAt(0)
Returns
head.obj
Linear search for
smallest value
O(n)
O(n)
O(n)
Slide data down
O(1)  Reverse
Order
head.remove()
Linear search then
remove smallest
We can definitely do better than these!!!
Priority Queues: Heaps
• Heap: has 2 completely different meanings
1. Classic data structure used to implement priority queues
2. Memory space used for dynamic allocation
We will study the data structure (not dynamic memory allocation)
• Heap data structure: a complete binary tree in which every
node’s value is less than or equal to the values of its children
• Review: a complete binary tree is a tree in which
1. Every node has at most two children (binary)
2. The tree is entirely filled except for the bottom level which is
filled from left to right (complete)
– Longest path is ceiling(log n) for n nodes
Heap: Example
Root = Smallest element
2
3
5
9
14
10
12
11
7
16
Last filled position
(not necessarily the last object added)
8
Next open spot
Maintaining the Heap: Addition
2
Add element: 4
3
5
9
14
10
12
11
7
16
4
8
New element in
next open spot.
Place new element in next available position,
then fix it by “percolating up”
Maintaining the Heap: Addition (cont.)
2
3
5
9
14
10
12
11
4
16
2
8
3
7
4
After first iteration (swapped with 7)
9
14
Percolating up:
while new value is less than parent,
swap value with parent
10
12
11
5
16
8
7
After second iteration (swapped with 5)
New value not less than parent  Done
Maintaining the Heap: Removal
• Since each node’s value is less than or equal to the values
of its children, the root is always the smallest element
• Thus, the PQueue methods getFirst and removeFirst
access and remove the root node, respectively
• Heap removal (removeFirst):
1. Replace root with the element in the last filled position
2. Fix heap by “percolating down”
Maintaining the Heap: Removal
removeFirst :
2
1. Move value in last
element into root
2. Percolate down
Root = Smallest element
3
5
9
14
10
12
11
7
16
Last filled position
8
Maintaining the Heap: Removal (cont.)
16
3
5
9
14
10
12
7
3
8
16
11
5
Root object removed
(16 copied to root and last node removed)
9
14
Percolating down:
while greater than smallest child
swap with smallest child
10
12
7
11
After first iteration (swapped with 3)
8
Maintaining the Heap: Removal (cont.)
3
9
5
16
14
10
12
7
3
8
9
11
5
After second iteration (moved 9 up)
12
14
Percolating down:
while greater than smallest child
swap with smallest child
10
16
7
8
11
After third iteration (moved 12 up)
Reached leaf node  Stop percolating
Maintaining the Heap: Removal (cont.)
3
Root = New smallest element
9
5
12
14
10
16
11
New last filled position
7
8
Heap Representation
• Recall that a complete binary tree can be efficiently
represented by an array or a vector:
– Children of node at index i are stored at indices 2i + 1 and 2i + 2
– Parent of node at index i is at index floor((i - 1) / 2)
2
3
5
9
14
10
12
11
7
8
16
0
1
2
3
2
3
5
9 10 7 8 14 12 11 16
4
5
6
7
8
9
10
Heap Implementation: add (cont.)
void addElement(struct dyArray * da, EleType val) {
int pos = dyArraySize(da);
// Get index of next open spot.
dyArrayAdd(da, val);
// add element at end
// Get parent index (up the tree).
int up = (pos – 1) / 2;
...
}
Example: add 4 to the heap
Prior to addition, size = 11
Parent position
Next open spot
(up)
(pos)
0
1
2
3
2
3
5
9 10 7 8 14 12 11 16 4
4
5
6
7
8
9
10 11
A couple of Useful Routines
void swap (struct dyArray * da, int i, in j) {
/* swap elements at I and j */
EleType temp = dyArrayGet(da, i);
dyArraySet(da, i, dyArrayGet(da, j));
dyArraySet(da, j, temp);
}
int indexSmallest (struct dyArray *da, int i, int j) {
/* return index of smallest element */
if (LT(dyArrayGet(da, i), dyArrayGet(da, j)))
return i;
return j;
}
Heap Implementation: add (cont.)
void add(struct dyArray * da, EleType val) {
...
/* While not at root and new value is less than parent. */
while ((pos != 0) && (indexSmallest(da, pos, up) == pos)) {
swap(da, pos, up); /* swap values of parent and child */
pos = up; up = (pos - 1) / 2; /* Move position and compute parent idx.*/
...
}
After first iteration: “swapped” new value (4) with parent (7)
New parent value: 5
up
pos
0
1
2
3
2
3
5
9 10 4 8 14 12 11 16 7
4
5
6
7
8
9
10 11
Heap Implementation: add (cont.)
void add(struct dyArray * da, EleType val) {
...
/* While not at root and new value is less than parent. */
while ((pos != 0) && (indexSmallest(da, pos, up) == pos)) {
swap(da, pos, up); // swap values of parent and child
pos = up; up = (pos - 1) / 2; // Move position and compute parent idx.
...
}
After second iteration: “swapped” new value (4) with parent (5)
New parent value: 2
up
pos
0
1
2
3
2
3
4
9 10 5 8 14 12 11 16 7
4
5
6
7
8
9
10 11
Heap Implementation: add (cont.)
void add(struct dyArray * da, EleType val) {
...
/* While not at root and new value is less than parent. */
while ((pos != 0) && (indexSmallest(da, pos, up) == pos)) {
. . .
} /* End while: reached root or parent is smaller than new value. */
/* Done. */
}
Second part of while test fails: stop iteration and add new value
up
pos
0
1
2
3
2
3
4
9 10 5 8 14 12 11 16 7
4
5
6
7
8
9
10 11
Heap Implementation: add (cont.)
2
3
5
9
10
7
8
up
14
12
11
4
16
pos
0
1
2
3
2
3
5
9 10 7 8 14 12 11 16 4
4
5
6
7
8
9
10 11
Heap Implementation: add (cont.)
2
3
5
9
10
up
4
8
pos
14
12
11
7
16
0
1
2
3
2
3
5
9 10 4 8 14 12 11 16 7
4
5
6
7
8
9
10 11
Heap Implementation: add (cont.)
2
3
4
up
9
14
10
12
11
pos
5
8
7
16
0
1
2
3
2
3
4
9 10 5 8 14 12 11 16 7
4
5
6
7
8
9
10 11
Heap Implementation: add (cont.)
2
3
4
9
14
10
12
11
pos
5
8
7
16
0
1
2
3
2
3
4
9 10 5 8 14 12 11 16 7
4
5
6
7
8
9
10 11
Heap Implementation: removeFirst
void removeFirst(struct dyArray * da) {
int last = dyArraySize(da) – 1;
if (last != 0)
dyArraySet(da, 0, dyArrayGet(da, last)); //
// Copy the last element to
the first position.
// Remove last element.
// Rebuild heap property.
dyArrayRemoveAt(da, last);
adjustHeap(dyArraySize(da), 0);
}
First element
Last element
(elementAt(0))
(last)
0
1
2
3
2
3
4
9 10 5 8 14 12 11 16 7
0
1
2
3
7
3
4
9 10 5 8 14 12 11 16
4
4
5
5
6
6
7
7
8
8
9
9
10 11
10 11
Heap Implementation: adjustHeap
void adjustHeap(EleType * data, int max, int idx) {
What’s next: val > min  Copy min to parent spot (idx)
Move idx to child
child (left child smallest)
idx
val = 7
max
min = 3
0
1
2
3
7
3
4
9 10 5 8 14 12 11 16
4
5
6
7
8
9
10 11
Heap Implementation: adjustHeap (cont.)
2
3
4
9
14
10
12
11
5
8
7
16
last
0
1
2
3
2
3
4
9 10 5 8 14 12 11 16 7
4
5
6
7
8
9
10 11
Heap Implementation: adjustHeap (cont.)
7
3
4
9
10
5
8
New root
14
12
11
16
max
0
1
2
3
7
3
4
9 10 5 8 14 12 11 16
4
5
6
7
8
9
10 11
Heap Implementation: adjustHeap (cont.)
7
3
val > min  Copy min to parent spot (idx)
Move idx to child
4
val = 7
9
10
5
8
Smallest child
14
12
11
(min = 3)
16
max
0
1
2
3
7
3
4
9 10 5 8 14 12 11 16
4
5
6
7
8
9
10 11
Heap Implementation: adjustHeap (cont.)
3
7
val > min  Copy min to parent spot (idx)
Move idx to child
4
val = 7
9
10
5
8
idx
14
12
11
16
max
0
1
2
3
3
7
4
9 10 5 8 14 12 11 16
4
5
6
7
8
9
10 11
Heap Implementation: adjustHeap (cont.)
3
7
If larger than both children
Done
4
val = 7
9
10
5
8
idx
14
12
11
16
max
Smallest child
(min = 9)
0
1
2
3
3
7
4
9 10 5 8 14 12 11 16
4
5
6
7
8
9
10 11
AdjustHeap - Write recursively
void adjustHeap (EleType * data, int max, int pos) {
int leftChild = pos * 2 + 1; int rightChild = pos * 2 + 2;
if (rightChild < max) { // have two children
// get index of smallest
// compare smallest child to pos
// if necessary, swap and call adjustHeap(max, child)
} else if (leftChild < max) { // have only one child
// compare child to parent
// if necessary, swap and call adjustHeap(max, child)
} // else no children, we are at bottom
}
Priority Queues: Performance Evaluation
SortedVector
addElement
getFirst
removeFirst
O(n)
SortedList
Heap
Binary search
Slide data up
O(n)
O(log n)
Linear search
Percolate up
O(1)
O(1)
O(1)
elementAt(0)
Returns head.obj
Get root node
O(1)
O(log n)
head.remove()
Percolate down
O(n)
Slide data down
O(1): Reverse Order
So, which is the best implementation of a priority queue?
Priority Queues: Performance Evaluation
• Remember that a priority queue’s main purpose is rapidly
accessing and removing the smallest element!
• Consider a case where you will insert (and ultimately
remove) n elements:
– ReverseSortedVector and SortedList:
Insertions: n * n = n2
Removals: n * 1 = n
Total time: n2 + n = O(n2)
– Heap:
Insertions: n * log n
Removals: n * log n
Total time: n * log n + n * log n = 2n log n = O(n log n)