Scribd
Upload
72 views5 pages

Heap Tree

A heap is a special tree-based data structure that is implemented as an array. It is a complete binary tree where the root node has the greatest (max heap) or least (min heap) value among its children. Algorithms are provided to create, insert, and delete from max and min heaps by comparing nodes and swapping if the heap property is violated.

Uploaded by

Abhijit Pal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
72 views5 pages

Heap Tree

A heap is a special tree-based data structure that is implemented as an array. It is a complete binary tree where the root node has the greatest (max heap) or least (min heap) value among its children. Algorithms are provided to create, insert, and delete from max and min heaps by comparing nodes and swapping if the heap property is violated.

Uploaded by

Abhijit Pal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Heap Tree:

A Heap is a special Tree-based data structure in which the tree is a complete binary tree
and it is implemented in array as sequential representation rather than linked
representation. In sequential representation of complete binary tree, the first element of
array a[0] will be the root. The left and right child of the node a[k] will be a[2k+1] and
a[2k+2].

Generally, Heaps can be of two types:


 Max-Heap: In a Max-Heap the key present at the root node must be greatest among
the keys present at all of it’s children. The same property must be recursively true for
all sub-trees in that Binary Tree.
 Min-Heap: In a Min-Heap the key present at the root node must be minimum among
the keys present at all of it’s children. The same property must be recursively true for
all sub-trees in that Binary Tree.
The max heap creation algorithm
Step 1 – Create a complete binary tree, the first element of array a[0] will be the root. The
left and right child of the node a[k] will be a[2k+1] and a[2k+2].
Step 2 − Compare the value of this child node with its parent.
Step 3 − If value of parent is less than child, then swap them.
Step 4 − Repeat step 2 & 3 until max Heap property holds.
73 74 81 79 90 93
0 1 2 3 4 5

The min heap creation algorithm


Step 1 – Create a complete binary tree, the first element of array a[0] will be the root. The
left and right child of the node a[k] will be a[2k+1] and a[2k+2].
Step 2 − Compare the value of this child node with its parent.
Step 3 − If value of parent is greater than child, then swap them.
Step 4 − Repeat step 2 & 3 until max Heap property holds.
90 85 20 10 15 22 18
0 1 2 3 4 5 6
Max Heap Insertion Algorithm
Place the new element one spot after the last element (the new element becomes the
rightmost element of the bottom level).
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Min Heap Insertion Algorithm


Place the new element one spot after the last element (the new element becomes the
rightmost element of the bottom level).
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is greater than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.
Max Heap Deletion Algorithm
Let us derive an algorithm to delete from max heap. Deletion in Max Heap always happens
at the root to remove the Maximum value.
Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Min Heap Deletion Algorithm


Let us derive an algorithm to delete from min heap. Deletion in Min Heap always happens
at the root to remove the minimum value.
Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is greater than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

You might also like