Priority Queues and Binary Heap

  1. Introduction
  2. Array Representation of Binary Heap
  3. MinHeap vs. MaxHeap
  4. Insert
  5. DeleteMax
  6. Preserving the Heap Order Property
  7. BuildHeap
  8. HeapSort
  9. Analysis

4. Insert

Inserting a new item into a binary heap:

  1. Store the new item at the last empty cell in the array (the levels are occupied from left to right)

  2. Lift the new item into its correct position by performing swaps with its father until the heap order property is satisfied.


Building a heap by inserting items one at the time

To build a heap with insert routine is straightforward. Just insert one at the time all the items at the end of the heap and lift each inserted item into its correct position.

Exercise: Insert

Insert the stream of keys into an originally empty binary heap. The heap is depicted in binary tree representation even though the implementation is an array starting from index 1 (the root node).
Each record stored into Heap is represented by a key that shows its priority. You can drag & drop the keys from the array into the heap and restore heap property after each insertion. If you drag & drop a key in heap on top of another one, the records are swapped, which corresponds to the operations in the "do" loop.
Algorithm 1 MaxHeap-Insert(A, key)

heap-size[A] ← heap-size[A] + 1
i ← heap-size[A] - 1
while i > 0 and A[Parent(i)] < key
do A[i] ← A[Parent(i)]
i ← Parent(i)
A[i] ← key

Previous Chapter: MinHeap vs. MaxHeap Next Chapter: DeleteMax

This document was last updated 30.5.2011. Please send your comments to Mikko Laakso, Ari Korhonen, and Ville Karavirta.