Next:6.1.1
Implementation of Insert and DeleteminUp:6.
Priority QueuesPrevious:6.
Priority Queues
6.1 Binary Heaps
Heaps (occasionally called as partially ordered trees) are a very popular
data structure for implementing priority queues.

A heap is either a minheap or a maxheap. A minheap supports the insert
and deletemin operations while a maxheap supports the insert and deletemax
operations.

Heaps could be binary or dary. Binary heaps are special forms of binary
trees while dary heaps are a special class of general trees.

Binary heaps were first introduced by Williams in 1964.
REF. J.W.J. Williams. Algorithm 232: Heapsort. Communications of
the ACM, Volume 7, 1964, pp 347348
We discuss binary minheaps. The discussion is identical for binary
maxheaps.
DEF. A binary heap is a complete binary tree with elements from
a partially ordered set, such that the element at every node is less than
(or equal to) the element at its left child and the element at its right
child. Figure 6.1 shows and example
of a heap.
Figure 6.1: An example of a heap and its array representation


Since a heap is a complete binary tree, the elements can be conveniently
stored in an array. If an element is at position i in the array, then the
left child will be in position 2i and the right child will be in position
2i + 1. By the same token, a nonroot element at position i will
have its parent at position

Because of its structure, a heap with height k will have between 2^{k}and 2^{k
+ 1}  1 elements. Therefore a heap with n elements will have height
= log_{2}
n

Because of the heap property, the minimum element will always be present
at the root of the heap. Thus the findmin operation will have worstcase
O (1) running time.
Next:6.1.1
Implementation of Insert and DeleteminUp:6.
Priority QueuesPrevious:6.
Priority Queues
eEL,CSA_Dept,IISc,Bangalore