heap

The data structure for Priority Queue

Why?

What if we ONLY want to search the highest priority element?

We can achieve it by

1. priority ordered list: We pay the price on insertion though. Adding an element needs O(n) to keep the list in order.

2. multiple lists: each priority has a list.

3. heap: an efficient way to solve priority queue issue

insert, deleteHighestP (delete highest priority object) are the two primary functions.

PQ applications

printer

network routers

os scheduler

simulation

select nth

how about emergency room?

What is Heap?

Heap is a tree with the following structure rules.

1. complete binary tree

   1. numbering is simple, root = n, L = 2n+1, R = 2n+2

2. smallest priority (key) at the top (or largest depends on order) -- heap order

The special characteristic of heap is that a heap can be easily represented in an array with root in index 0. Why is it a big deal? Because array is fastest data structure for many applications.

If you think of it, the "complete binary tree" and "array representation" are two sides of a coin. If it is not a complete binary tree, I don't know how to easily represent it in an array. The reverse is also true.

Given an object in the array with index p, its left child has index 2p+1 and right child has index 2p+2.

Conversely, the parent index of an object with index k is floor((k+1)/2) - 1 or better yet, floor((k-1)/2)

In many references, min-heap refers to smallest priority is at the top, max-heap refers to largest priority at the top.

Heap Algorithms

<< must have operations >>

insert percolation up

find empty hole (always the last one - rule #1 complete binary tree), try insert there, bubble up based on rule #2

deleteMin/deleteMax percolation down

remove root (always min - rule #2 heap order), try to put the "last item" there, bubble down based on rule #2

<< as needed operations >>

increaseKey percolation down for min-heap, percolation up for max-heap

decreaseKey percolation up for max-heap, percolation down for min-heap

remove changeKey to highest priority => automatically bubble up to root

deleteMin

(very elegant algorithm)

Build a heap from large data

Approach #1 : insert them all one at a time -- simple and stupid

Approach #2:

layout all node (i.e. put all in an array)

exam and percolate each parent node

(another elegant algorithm)

Limitations

• • find an element is like traverse the entire array

  • merge two heap is not as easy as merge to sorted queue.

  • Well, it is not too bad. How would you do it?

  • remove a non-root element needs more work

  • many other limitations too.

STL support

• part of queue

• empty, pop (deleteMin), push (insert), top, size

Discussions

1. The point of heap is that it is a "special purpose" data structure. It supports limited functions very well, but not really a general purpose data structure. Understanding its plus and minus will equip us to make the right choice when situation arises.

   1. Since heap can get us the highest priority element, by repeating the deleteMin process, we can achieve "sorting". That's appropriately called heap sort.