Answer to Question #247472 in Algorithms for Michael Sampson

Question

a.      Describe the concept of a Binary heap and the heap order property. [10 marks]

b.     Explain the use of the binary heap as an effective implementation for a priority queue [10 MARKS]

Answer 1

a.

A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:

• the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
• the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.

b.

The binary heap is a data structure that can efficiently support the basic priority-queue operations. In a binary heap, the items are stored in an array such that each key is guaranteed to be larger than (or equal to) the keys at two other specific positions.