**Heap Data Structure-**

In data structures,

- Heap is a specialized data structure.
- It has special characteristics.
- A heap may be implemented using a n-ary tree.

In this article, we will discuss implementation of heap using a binary tree.

**Binary Heap-**

A binary heap is a **Binary Tree** with the following two properties-

- Ordering Property
- Structural Property

**1. Ordering Property-**

By this property,

- Elements in the heap tree are arranged in specific order.
- This gives rise to two types of heaps- min heap and max heap.

**2. Structural Property-**

By this property,

- Binary heap is an almost complete binary tree.
- It has all its levels completely filled except possibly the last level.
- The last level is strictly filled from left to right.

**Types of Binary Heap-**

Depending on the arrangement of elements, a binary heap may be of following two types-

- Max Heap
- Min Heap

**1. Max Heap-**

- Max Heap conforms to the above properties of heap.
- In max heap, every node contains greater or equal value element than its child nodes.
- Thus, root node contains the largest value element.

**Example-**

Consider the following example of max heap-

This is max heap because-

- Every node contains greater or equal value element than its child nodes.
- It is an almost complete binary tree with its last level strictly filled from left to right.

**2. Min Heap-**

- Min Heap conforms to the above properties of heap.
- In min heap, every node contains lesser value element than its child nodes.
- Thus, root node contains the smallest value element.

**Example-**

Consider the following example of min heap-

This is min heap because-

- Every node contains lesser value element than its child nodes.
- It is an almost complete binary tree with its last level strictly filled from left to right.

**Array Representation of Binary Heap-**

A binary heap is typically represented as an array.

For a node present at index ‘i’ of the array Arr-

**If indexing starts with 0,**

- Its parent node will be present at array location = Arr [ i/2 ]
- Its left child node will be present at array location = Arr [ 2i+1 ]
- Its right child node will be present at array location = Arr [ 2i+2 ]

**If indexing starts with 1,**

- Its parent node will be present at array location = Arr [ ⌊i/2⌋ ]
- Its left child node will be present at array location = Arr [ 2i ]
- Its right child node will be present at array location = Arr [ 2i+1 ]

**Important Notes-**

**Note-01:**

- Level order traversal technique may be used to achieve the array representation of a heap tree.
- Array representation of a heap never contains any empty indices in between.
- However, array representation of a binary tree may contain some empty indices in between.

**Note-02:**

Given an array representation of a binary heap,

- If all the elements are in descending order, then heap is definitely a max heap.
- If all the elements are not in descending order, then it may or may not be a max heap.
- If all the elements are in ascending order, then heap is definitely a min heap.
- If all the elements are not in ascending order, then it may or may not be a min heap.

**Note-03:**

- In max heap, every node contains greater or equal value element than all its descendants.
- In min heap, every node contains smaller value element that all its descendants.

**PRACTICE PROBLEMS BASED ON HEAP DATA STRUCTURE-**

**Problems-**

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap? (GATE CS 2009)

- 25, 14, 16, 13, 10, 8, 12
- 25, 12, 16, 13, 10, 8, 14
- 25, 14, 12, 13, 10, 8, 16
- 25, 14, 13, 16, 10, 8, 12

**Solutions-**

**Part-01: 25, 14, 16, 13, 10, 8, 12-**

The given array representation may be converted into the following structure-

Clearly,

- It is a complete binary tree.
- Every node contains a greater value element than its child nodes.

Thus, the given array represents a max heap.

**Part-02: 25, 12, 16, 13, 10, 8, 14-**

The given array representation may be converted into the following structure-

Clearly,

- It is a complete binary tree.
- Every node does not contain a greater value element than its child nodes. (Node 12)
- So, it is not a max heap.
- Every node does not contain a smaller value element than its child nodes.
- So, it is not a min heap.

Thus, the given array does not represents a heap.

**Part-03: 25, 14, 12, 13, 10, 8, 16-**

The given array representation may be converted into the following structure-

Clearly,

- It is a complete binary tree.
- Every node does not contain a greater value element than its child nodes. (Node 12)
- So, it is not a max heap.
- Every node does not contain a smaller value element than its child nodes.
- So, it is not a min heap.

Thus, the given array does not represents a heap.

**Part-04: 25, 14, 13, 16, 10, 8, 12-**

The given array representation may be converted into the following structure-

Clearly,

- It is a complete binary tree.
- Every node does not contain a greater value element than its child nodes. (Node 14)
- So, it is not a max heap.
- Every node does not contain a smaller value element than its child nodes.
- So, it is not a min heap.

Thus, the given array does not represents a heap.

To gain better understanding about Heap Data Structure,

**Next Article-** **Heap Operations**

Get more notes and other study material of **Data Structures**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.