Last Updated : 02 Nov, 2023
Summarize
Comments
Improve
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
Next Article
Difference between Heaps and Sorted Array
Please Login to comment...
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 7 min read 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 10 min read 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 2 min read 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 13 min read 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 9 min read 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 13 min read 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 6 min read 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[] = { 5 min read 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 11 min read Split array into K Subarrays to minimize sum of difference between min and max Given a sorted array arr[] of size N and integer K, the task is to split the array into K non-empty subarrays such that the sum of the difference between the maximum element and the minimum element of each subarray is minimized. Note: Every element of the array must be included in one subarray and each subarray should be non-empty. Examples: Input: 6 min read Longest Subsequence with difference between max and min at most K Given an array arr[] of size N and a non-negative integer K, the task is to find the length of the longest subsequence such that the difference between the maximum and the minimum of the subsequence is at most K. Examples: Input: arr[] = {1, 3, 5, 4, 2}, N = 5, K = 3Output: 4Explanation: If we consider, the sequence {1, 3, 4, 2}. The subsequence ma 5 min read Minimum difference between max and min of all K-size subsets Given an array of integer values, we need to find the minimum difference between the maximum and minimum of all possible K-length subsets. Examples : Input : arr[] = [3, 5, 100, 101, 102] K = 3 Output : 2 Explanation : Possible subsets of K-length with their differences are, [3 5 100] max min diff is (100 - 3) = 97 [3 5 101] max min diff is (101 - 7 min read k size subsets with maximum difference d between max and min C/C++ Code // C++ code to find no. of subsets with // maximum difference d between max and #include <bits/stdc++.h> using namespace std; // function to calculate factorial of a number int fact(int i) { if (i == 0) return 1; return i * fact(i - 1); } int ans(int a[], int n, int k, int x) { if (k > n || n < 1) return 0; sort(a, a + n); in 15+ min read Longest subarray such that the difference of max and min is at-most one Given an array of n numbers where the difference between each number and the previous one doesn't exceed one. Find the longest contiguous subarray such that the difference between the maximum and minimum number in the range doesn't exceed one. Examples: Input : {3, 3, 4, 4, 5, 6} Output : 4 The longest subarray here is {3, 3, 4, 4} Input : {7, 7, 7 7 min read Divide a sorted array in K parts with sum of difference of max and min minimized in each part Given an ascending sorted array arr[] of size N and an integer K, the task is to partition the given array into K non-empty subarrays such that the sum of differences of the maximum and the minimum of each subarray is minimized. Examples: Input: arr[] = {4, 8, 15, 16, 23, 42}, K = 3 Output: 12 Explanation: The given array can be split into three su 7 min read Min and max length subarray having adjacent element difference atmost K Given an array arr[] and an integer K, the task is to find the maximum and minimum length subarray such that the difference between adjacent elements is at most K.Examples: Input: arr[] = {2, 4, 6}, K = 2 Output: 3, 3 Explanation: Minimum and Maximum length subarray such that difference between adjacent elements is at most is 3, which is {2, 4, 2}I 9 min read Longest subsequence such that difference of max and min is at-most K Given an array arr[] of length N, the task is to find the length of longest subsequence such that the difference of its maximum element and minimum element is not more than an integer K. A sequence a is a subsequence of a sequence b if ????a can be obtained from b by deletion of several (possibly, zero) elements. For example, [3,1][3,1] is a subseq 8 min read Nth term where K+1th term is product of Kth term with difference of max and min digit of Kth term Given two integers N and D, the task is to find the value of F(N) where the value of F(1) is D, where F(K) is given as: [Tex]F(K+1) = F(K) * (Max_{Digit}(F(K)) - Min_{Digit}(F(K)))[/Tex] Examples: Input: N = 3, D = 487 Output: 15584 Explanation: As F(1) = 487, F(2) = 487 * (maxDigit(487) - minDigit(487)) = 487 * 4 = 1948 F(3) = 1948 * (maxDigit(194 6 min read Divide a sorted array in K parts with sum of difference of max and min minimized in each part - Set 2 Given an ascending sorted array arr[] of size N and an integer K, the task is to partition the given array into K non-empty subarrays such that the sum of differences of the maximum and the minimum of each subarray is minimized. Examples: Input: arr[] = { 10, 20, 70, 80 }, N = 4, K = 2Output: 20Explanation: The given array can be split in the follo 11 min read Difference of Max and Min Subtree Sums in Tree Nodes Given a tree containing N nodes in the form of an array P where Pi represents the parent of the i-th node and P1 = -1 as the tree is rooted at node 1. Also given an array vals which consists of the value of the ith node from 1 to N. For each node in the tree find the difference between the maximum and minimum subtree sum. Examples: Input: N = 6, pa 8 min read Check presence of integer between min and max of Array that divide all Array elements Given an array A[] of size N, the task is to check if there exists any integer that divide all the elements of that array and lies in the range of minimum and maximum elements (both included) of that array. Examples: Input: A = {27, 6, 9, 3, 21}Output: 1Explanation: Here, 3 lies between min(3) and max(27) of this array, and divides all elements of 5 min read What's the relationship between "a" heap and "the" heap? A Heap:"A Heap" refers to the heap data structure where we can store data in a specific order. Heap is a Tree-based data structure where the tree is a complete binary tree. Heap is basically of two types: Max-Heap: The key at the Root node of the tree will be the greatest among all the keys present in that heap and the same property will be follow 15+ min read Count number of Subsequences in Array in which X and Y are min and max elements Given an array arr[] consisting of N unique elements, the task is to return the count of the subsequences in an array in which the minimum element is X and the maximum element is Y. Examples: Input: arr[] = {2, 4, 6, 7, 5}, X = 2, Y = 5Output: 2Explanation: Subsequences in which the minimum element is X and the maximum element is Y are {2, 5}, {2, 11 min read Rank of remaining numbers in Array by replacing first and last with max and min alternatively Given an array arr[ ] of size N, the task is to find the rank of the remaining element in an array after performing the given operation: In each operation choose elements from both ends and delete them and insert the max of those values at the position of the left element and move one step towards the center from both ends and keep performing this 8 min read Min and Max in a List in Java Given an unsorted list of integers, find maximum and minimum values in it. Input : list = [10, 4, 3, 2, 1, 20] Output : max = 20, min = 1 Input : list = [10, 400, 3, 2, 1, -1] Output : max = 400, min = -1Sorting This is least efficient approach but will get the work done. The idea is to sort the list in natural order, then the first or last element 5 min read Sum of width (max and min diff) of all Subsequences Given an array A[] of integers. The task is to return the sum of the width of all subsequences of A. For any sequence S, the width of S is the difference between the maximum and minimum elements of S. Note: Since the answer can be large, print the answer modulo 10^9 + 7. Examples: Input : A[] = {1, 3, 2} Output : 6 Subsequences are {1}, {2}, {3}, { 5 min read Number formed by adding product of its max and min digit K times Given two integers N and K, the task is to print the number formed by adding product of its max and min digit, K times. [Tex]M(N+1) = M(N) + maxDigit(M(N)) * minDigit(M(N)) [/Tex] Examples Input: N = 14, K = 3 Output: 26 Explanation: M(0)=14 M(1)=14 + 1*4 = 18 M(2)=18 + 1*8 = 26 Input: N = 487, K = 100000000 Output: 950 Approach A natural intuition 5 min read Maximize sum of max and min of each of K Arrays obtained by dividing given Array into given sizes Given two arrays, arr[] of N size and div[] of size K. Divide arr[] into K different arrays, each of div[i] size. The task is to find the total sum after maximizing the sum of maximum and minimum of each divided array. Examples: Input: arr[] = {3, 1, 7, 4}, div[] = {1, 3}, N = 4, K = 2Output: 19Explanation: Divide the array in the following way: {7 9 min read Last remaining value from 2^N integers after deleting Max from even sum and Min from odd sum pair Given a Non-Negative integer N, denoting the first 2N positive integers where consecutive integers starting from 1 are paired with each other, the task is to find the last number remaining after performing the following operations: Consider a pair (x, y) of two consecutive integers which are not yet deleted from the 2N integers.If the sum of two in 5 min read Number of pairs of Array where the max and min of pair is same as their indices Given an array A[] of N integers, the task is to calculate the total number of pairs of indices (i, j) satisfying the following conditions - 1 ? i < j ? Nminimum(A[i], A[j]) = imaximum(A[i], A[j]) = j Note: 1-based indexing is considered. Examples: Input: N = 4, A[] = {1, 3, 2, 4}Output: 2Explanation: First pair of indices is (1, 4), As minimum( 6 min read
Article Tags :
- Data Structures
- Difference Between
- DSA
- Heap
Practice Tags :
- Data Structures
- Heap
- Tree
