What is Heap data structure? Explain with an example.

Heap

Heap data structure is a binary tree with some special structural orientation often known as complete binary tree. Heap data structure or heap attribute of an array is used in heap sorting. To understandheap we need to understand binary tree and some related terms. Let us understandthese one by one.

Binary Tree

Binary Tree is the simplest form of tree data structure where each node can have max of two children, known as left and right. The node of a Binary Tree is formed with two pointers to point child nodes named as left and right.

 struct binary_tree_node_t {
   int value;
   struct binary_tree_node_t * left;
   struct struct binary_tree_node_t * right;
 };
 

Full Binary Tree

A full Binary tree is a tree in which everynode other than the leaves has two children.     

Complete binary tree

   A complete binary tree is similar to a full binary tree, but with two major differences 

• Every level must be completely filled
• All the leaf elements must lean towards the left.
• The last leaf element might not have a right sibling i.e. a complete binary tree doesn’t have to be a full binary tree. 

Here are some example binary tree nodes. Some qualifies the property of complete binary tree.

Here are some example 2nd level binary trees. Some qualifies the property of complete binary tree.

Heap Data Structure

Heap is a special binary tree based data structure. A binary tree is said to follow a heap data structure if it is a complete binary tree. There are two types of heap structure. Max heap and min heap.

Max heap/Descending heap

Max heap is a heap structure where parent element is always larger than child elements. This ordering rule is maintained in the entire tree. Thus all the parent elements are larger than children elements in any level of the tree and the root contains the largest value.

Min heap/Assending heap

Min heap is a heap structure where parent element is lower than child elements. Thus root of the min heap contains the lowest value and the further we go to the depth, values are larger.

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›