Difference between Min Heap and Max Heap

Last Updated : 02 Nov, 2023

A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Since a heap is a complete binary tree, a heap with N nodes has log N height. It is useful to remove the highest or lowest priority element. It is typically represented as an array. There are two types of Heaps in the data structure.

Min-Heap

In a Min-Heap the key present at the root node must be less than or equal among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. In a Min-Heap the minimum key element present at the root. Below is the Binary Tree that satisfies all the property of Min Heap.

Max Heap

In a Max-Heap the key present at the root node must be greater than or equal among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. In a Max-Heap the maximum key element present at the root. Below is the Binary Tree that satisfies all the property of Max Heap.

Difference between Min Heap and Max Heap

	Min Heap	Max Heap
1.	In a Min-Heap the key present at the root node must be less than or equal to among the keys present at all of its children.	In a Max-Heap the key present at the root node must be greater than or equal to among the keys present at all of its children.
2.	In a Min-Heap the minimum key element present at the root.	In a Max-Heap the maximum key element present at the root.
3.	A Min-Heap uses the ascending priority.	A Max-Heap uses the descending priority.
4.	In the construction of a Min-Heap, the smallest element has priority.	In the construction of a Max-Heap, the largest element has priority.
5.	In a Min-Heap, the smallest element is the first to be popped from the heap.	In a Max-Heap, the largest element is the first to be popped from the heap.

Applications of Heaps:

Heap Sort: Heap Sort is one of the best sorting algorithms that use Binary Heap to sort an array in O(N*log N) time.
Priority Queue: A priority queue can be implemented by using a heap because it supports insert(), delete(), extractMax(), decreaseKey() operations in O(log N) time.
Graph Algorithms: The heaps are especially used in Graph Algorithms like Dijkstra’s Shortest Path and Prim’s Minimum Spanning Tree.

Performance Analysis of Min-Heap and Max-Heap:

Get Maximum or Minimum Element: O(1)
Insert Element into Max-Heap or Min-Heap: O(log N)
Remove Maximum or Minimum Element: O(log N)

prashant_srivastava

Improve

Difference between Heaps and Sorted Array

Similar Reads

Find min and max values among all maximum leaf nodes from all possible Binary Max Heap

Given a positive integer N, the task is to find the largest and smallest elements, from the maximum leaf nodes of every possible binary max-heap formed by taking the first N natural numbers as the nodes' value of the binary max-heap. Examples: Input: N = 2Output: 1 1Explanation: There is only one maximum binary heap with the nodes {1, 2}: In the ab

Convert Min Heap to Max Heap

Given an array representation of min Heap, convert it to max Heap. Examples: Input: arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9} 3 / \ 5 9 / \ / \ 6 8 20 10 / \ /12 18 9 Output: arr[] = {20, 18, 10, 12, 9, 9, 3, 5, 6, 8} 20 / \ 18 10 / \ / \ 12 9 9 3 / \ /5 6 8 Input: arr[] = {3, 4, 8, 11, 13}Output: arr[] = {13, 11, 8, 4, 3} Approach: To solve the p

Difference between Binary Heap, Binomial Heap and Fibonacci Heap

Binary Heap:A Binary Heap is a Binary Tree with following properties. It’s a complete binary tree i.e., all levels are completely filled except possibly the last level and the last level has all keys as left as possible. This property of Binary Heap makes them suitable to be stored in an array. A Binary Heap is either Min Heap or Max Heap. In a Min

Heap Sort for decreasing order using min heap

Given an array of elements, sort the array in decreasing order using min heap. Examples: Input : arr[] = {5, 3, 10, 1} Output : arr[] = {10, 5, 3, 1} Input : arr[] = {1, 50, 100, 25} Output : arr[] = {100, 50, 25, 1} Prerequisite: Heap sort using min heap. Algorithm : Build a min heap from the input data. At this point, the smallest item is stored

Count of subsequences with a sum in range [L, R] and difference between max and min element at least X

Given an array arr[] consisting of N positive integers and 3 integers L, R, and X, the task is to find the number of subsequences of size atleast 2 with a sum in the range [L, R], and the difference between the maximum and minimum element is at least X. (N≤15) Examples: Input: arr[] = {1 2 3}, L = 5, R = 6, X = 1Output: 2Explanation: There are two

Find absolute difference between product of rowwise and columnwise min and max in given Matrix

Given a square matrix M[][] of size N x N, the task is to find the maximums & minimums of each of the rows and columns, multiply the corresponding maximums & minimums of each row with those of each column, Finally return the absolute difference of both of these. Examples: Input: M[][] = [ [ 3, 2, 5 ], [ 7, 5, 4 ], [ 7, 2, 9 ] ]Output: 11Exp

Generate N sized Array with mean K and minimum difference between min and max

Given two integers N and X, the task is to find an output array arr[] containing distinct integers of length N such that their average is K and the difference between the minimum and the maximum is minimum possible. Input: N = 4, X = 8Output :- 6 7 9 10Explanation: Clearly the mean of 6, 7, 9, 10 is 8 and The difference between the max and the min

Partition N into M parts such that difference between Max and Min part is smallest

Given two integers N and M, partition N into M integers such that the difference between the maximum and minimum integer obtained by the partition is as small as possible. Print the M numbers A1, A2....Am, such that: sum(A) = N.max(A)-min(A) is minimized. Examples: Input : N = 11, M = 3 Output : A[] = {4, 4, 3} Input : N = 8, M = 4 Output : A[] = {

Partition a set into two subsets such that difference between max of one and min of other is minimized

Given an array arr[] of N integers, the task is to split the array into two subsets such that the absolute difference between the maximum of first subset and minimum of second subset is minimum.Examples: Input: arr[] = {3, 1, 2, 6, 4} Output: 1 Explanation: Splitting the given array in two subsets, A = [1, 2, 4], B = [3, 6]. Difference of maximum o

Find Subarray ranges having difference between max and min exactly K

Given an array arr[] of length N and integer K, the task is to print subarray ranges (starting index, ending index) of the array where difference between max and min elements of the subarray is exactly K.( 1-based index ) Examples: Input: arr[] = {2, 1, 3, 4, 2, 6}, K = 2Output: (1, 3), (2, 3), (3, 5), (4, 5)Explanation: In the above array followin

Article Tags :

Practice Tags :