Transcript Heaps

Heaps
CS 367 – Introduction to Data Structures
Heap
• A heap is a tree that satisfies the following
conditions
– largest element in tree is located at the root
– each node has a larger value than its children
– tree is balanced and the leaves on the last
level are all as far left as possible
Valid Heaps
root
root
Z
Z
X
T
M
N
J
X
L
T
M
N
Invalid Heaps
root
root
X
X
Z
T
M
N
J
Z
L
Level 2 has a value higher than level 1
T
M
J
Nodes not all to left
Heap Applications
• Great for priority queues
– highest priority item always at the root
– just pop it off and re-sort the heap
• Can be used to sort data (called heap sort)
– put the data in a heap
– remove the root and re-sort
• keep repeating this until the heap is empty
• data was all removed in descending order
Implementing Heaps
• An elegant implementation is to use an
array
• Re-consider the breadth first search
– dequeue a node from the head of the queue
– enqueue the nodes children in queue
• What if the node wasn’t actually removed?
– instead, its children were just enqueued
Implementing Heaps
Z
X
T
M
N
J
L
0
1
queue Z
X
3
4
M T
N
2
5
J
6
L
Implementing Heaps
• The previous example shows that a tree
can be represented by an array
– the children of a node can be found with the
following equations
• child1 = index * 2 + 1
• child2 = index * 2 + 2
– the parent of a node can be found with the
following equation
• parent = (index - 1) / 2
// must be integer division
– this only works if the tree is balanced and all
nodes are as far left as possible
Implementing Heaps
• Basic class for a heap
class Heap {
Object[] heap;
int end;
public Heap(int size) {
heap = new Object[size];
end = 0;
}
public boolean insert(Object data);
public Object delete();
}
Inserting into Heap
• Place new node at very end of the array
– the index indicated by the end variable
• Compare the added node with its parent
– if it is greater than the parent, swap the two
elements
– repeat this process until it is no longer greater
than its parent or the root is reached
• This algorithm percolates an inserted node
toward the root as long as it is larger than
its parent
Inserting into Heap
private boolean insert(Object data) {
if(end == heap.length) { return false; }
heap[end] = data;
int pos = end;
int parent = (pos – 1) / 2;
while((pos != 0) && (heap[pos] > heap[parent]) {
swap(pos, parent);
pos = parent;
parent = (pos – 1) / 2;
}
end++;
return true
}
Deleting from Heap
• Remove the first element in the array
– this is the root of the tree – highest value
• Move the last element in the array into the root
position
• Compare the new root with both of its children
– if either of the nodes children are larger, swap it with
the largest one
– repeat this procedure until the node is larger than
both of its children or it has become a leaf
• Now the node “trickles” down the tree as long as
either of its children are larger than it
Deleting from Heap
public Object delete() {
if(end == 0) { return null; }
Object data = heap[0];
end--;
if(end == 0) { return; }
int pos = 0; int child = 1;
heap[pos] = heap[end];
while((child < end-1) &&
((heap[pos] < heap[child]) || (heap[pos] < heap[child+1]))) {
if(heap[child] < heap[child + 1]) { child++; }
swap(pos, child);
pos = child;
child = pos * 2 + 1;
}
if((child == end – 1) && (heap[pos] < heap[child]))
swap(pos, child);
}