Binary Heap – Data Structure

Usage

  • In Heapsort
  • In Priority Queue
  • Not the garbage collector storage (as provided by JVM)

Definition

A binary Heap is an array object. We can view that array object as a near complete binary tree. A binary tree is said to be a complete binary tree when all the nodes except possibly for the leaves has two children.

Screen Shot 2018-04-28 at 2.00.32 PM
Fig 1. An array of ten elements
Untitled Diagram (3)
Fig 2. The same array of Fig. 1, now seen as near complete binary tree

The height of a node in a heap is defined as the number of edges on the longest simple downward path from the node to a leaf.  For the element with value 22, the height is 3.

We define the height of the heap to be the height of its root. The height of heap in our example is 4.

Parent Node

For any element in array with index i, the parent of the node is i/2

Let’s consider the fourth element of the array shown in Fig. 1. The index is shown in the first row while the values are shown in the second row.

Here, index or i is 4. The parent should be i/2 or 4/2 = 2.

As we can verify in the Fig. 2, parent of the element at fourth index is indeed element at second index.

Left Child

For any element in array with index i, the left child of the node is 2 * i.

For element at fourth index, left child is the element at the eighth index which can be verified in the Fig. 2.

Right Child

For any element in array with index i, the right child of the node is 2 * i + 1.

For element at fourth index, right child is the element at the ninth index which can be verified in the Fig. 2.

Types

Max Heap

In a max-heap, the max-heap property is that for every node i other than the root,

A[Parent(i)] >= A(i)

This essentially means that the largest element in a max-heap is stored at the root, and the subtree rooted at a node contains values no larger than that contained at the node itself.

Copy of Untitled Diagram
Fig 3. Example of Max Heap (Notice that the largest value is at the top)

Min Heap

In a min-heap, the min-heap property is that for every node i other than the root,

A[Parent(i)] <= A(i)

This essentially means that the smallest element in a min-heap is stored at the root, and the subtree rooted at a node contains values larger or equal to that contained at the node itself.

Heap Operation

max_heapify

  • Assume that the trees rooted at left(i) and right(i) are max-heaps
  • If element A[i] violates the max-heap property, correct violation by “trickling” element A[i] down the tree, making the subtree rooted at index i a max-heap

 

 

Copy of Untitled Diagram (1)
Fig. 4 Example illustrating max_heapify

 

Pseudocode

Time Complexity

O(log(n))

log(n) is also the height of the tree. Time complexity as O(log(n)) can also be seen as each level has to be accessed once.

build_max_heap(A)

To build max heap out of an unordered array, we just need to call max_heapify for all elements.

We can safely start from n/2 to 1 as the elements from 1 to n/2 are leaves.

Pseudocode

Time Complexity

O(n)

max_heapify takes O(1) for nodes that are the level above the leaf nodes and O(l) for the elements that are l level up the leaf.

Proof

Screen Shot 2018-04-28 at 5.49.27 PM.png


Further Resource:

An awesome video lecture

Lecture Notes

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: