[go: up one dir, main page]
Scribd
Upload
103 views4 pages

5.2 Binary Heap An Min Heap

A binary heap is a complete binary tree structure used to efficiently store and retrieve the maximum or minimum element. It can be implemented as a min heap or max heap. A min heap stores the minimum key at the root. Binary heaps are commonly represented as arrays to allow efficient insertion, deletion, and retrieval of maximum/minimum elements in O(log n) time. They have applications in priority queues, sorting algorithms like heapsort, and graph algorithms like Dijkstra's algorithm.

Uploaded by

Ch Ahtasham
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
103 views4 pages

5.2 Binary Heap An Min Heap

A binary heap is a complete binary tree structure used to efficiently store and retrieve the maximum or minimum element. It can be implemented as a min heap or max heap. A min heap stores the minimum key at the root. Binary heaps are commonly represented as arrays to allow efficient insertion, deletion, and retrieval of maximum/minimum elements in O(log n) time. They have applications in priority queues, sorting algorithms like heapsort, and graph algorithms like Dijkstra's algorithm.

Uploaded by

Ch Ahtasham
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/ 4

Binary heap:

A Binary Heap is a complete Binary Tree which is used to store data efficiently to get the max or min
element based on its structure.
A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at the root must be minimum
among all keys present in Binary Heap..

Examples of Min Heap:


10 10
/ \ / \
20 100 15 30
/ / \ / \
30 40 50 100 40
How is Binary Heap represented?
A Binary Heap is a Complete Binary Tree. A binary heap is typically represented as an array.
 The root element will be at Arr[0].
th
 The below table shows indices of other nodes for the i node, i.e., Arr[i]:

Arr[(i-1)/2] Returns the parent node

Arr[(2*i)+1] Returns the left child node

Arr[(2*i)+2] Returns the right child node

Basic operations of binary heap:


1. Insertion in min heap data structure:

The new element is initially appended to the end of the heap (as the last element of the array). The heap
property is repaired by comparing the added element with its parent and moving the added element up a level
(swapping positions with the parent). This process is called "percolation up". The comparison is repeated until
the parent is larger than or equal to the percolating element.
2. Deletion in Min-Heap Data Structure:
Removing the smallest element (the root) from the min heap. The root is replaced by the last element in the
heap, and then the heap property is restored by swapping the new root with its smallest child until the parent
is smaller than both children or until the new root reaches a leaf node.
 Replace the root or element to be deleted with the last element.
 Delete the last element from the Heap.
 Since the last element is now placed at the position of the root node. So, it may not follow the heap
property. Therefore, heapify the last node placed at the position of the root.
 Suppose the Heap is a Min-Heap as:


 Min-Heap Data Structure

 The element to be deleted is root, i.e. 13.


 Process:
 The last element is 100.
 Step 1: Replace the last element with root, and delete it.

 Min-Heap Data Structure

 Step 2: Heapify root.


 Final Heap:


 Min-Heap Data Structure

Heapify operation on Min-Heap Data Structure:


A heapify operation can be used to create a min heap from an unsorted array. This is done by starting at the
last non-leaf node and repeatedly performing the “bubble down” operation until all nodes satisfy the heap
property.
Applications of Min-Heap Data Structure:
 Heap sort: Min heap is used as a key component in heap sort algorithm which is an efficient sorting
algorithm with a time complexity of O(nlogn).
 Priority Queue: A priority queue can be implemented using a min heap data structure where the element
with the minimum value is always at the root.
 Dijkstra’s algorithm: In Dijkstra’s algorithm, a min heap is used to store the vertices of the graph with
the minimum distance from the starting vertex. The vertex with the minimum distance is always at the
root of the heap.
 Merge K sorted arrays: Given K sorted arrays, we can merge them into a single sorted array efficiently
using a min heap data structure.

Advantages of Min-heap Data Structure:

 Efficient insertion and deletion: Min heap allows fast insertion and deletion of elements with a time
complexity of O(log n), where n is the number of elements in the heap.
 Efficient retrieval of minimum element: The minimum element in a min heap is always at the root of
the heap, which can be retrieved in O(1) time.
 Space efficient: Min heap is a compact data structure that can be implemented using an array or a binary
tree, which makes it space efficient.
 Sorting: Min heap can be used to implement an efficient sorting algorithm such as heap sort with a time
complexity of O(n log n).
 Priority Queue: Min heap can be used to implement a priority queue, where the element with the
minimum priority can be retrieved efficiently in O(1) time.
 Versatility: Min heap has several applications in computer science, including graph algorithms, data
compression, and database systems.

You might also like