Page 222 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 10: Heaps

Additionally, a heap is a “complete tree” -- a complete tree is one in which there are no Notes
gaps between leaves.
For instance, a tree with a root node that has only one child must have its child as the left
node.

More precisely, a complete tree is one that has every level filled in before adding a node to
the next level, and one that has the nodes in a given level filled in from left to right, with no

breaks.
10.6 Keywords

Binary Heap: A binary heap is a heap-ordered binary tree which has a very special shape called
a complete tree.

Discrete Event Simulation: One of the most important applications of priority queues is in discrete
event simulation.
d-Heap: d-heap is a priority queue data structure, a generalization of the binary heap in which
the nodes have d children instead of 2.
Heap: A heap is a specialized tree-based data structure that satisfies the heap property: if B is a

child node of A, then key(A) ≥ key(B).
10.7 Self Assessment

Fill in the blanks:
1. A heap is a partially sorted ......................... .
2. Complete trees and perfect trees are ......................... .
3. In a heap the ......................... is found at the root.
4. The ......................... method removes from a priority queue the item having the smallest
key.
5. The ......................... of an event depends on the type of that event.
6. The minimum priority item in a min-heap may always be found at ......................... of the
array.
7. The heap is one maximally-efficient implementation of an abstract data type called a

......................... .

8. ......................... calculations are used to find the parent and the children of a given node in
the tree.

10.8 Review Questions

1. What do you mean by heaps?
2. Explain complete binary tree.
3. Prove that “A complete binary tree of height h ≥ 0 contains at least 2 and at most 2 – 1
h
h+1
nodes.“
4. Prove that “The internal path length of a binary tree with n nodes is at least as big as the
internal path length of a complete binary tree with n nodes.”
5. Explain the implementation of binary heap.
6. Describe how will you put items into binary heaps.

LOVELY PROFESSIONAL UNIVERSITY 217