# 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. Fig 1. An array of ten elements 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. 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

### 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.

### 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 ## Further Resource:

An awesome video lecture

Lecture Notes