Heap Data Structure

DSA for Beginners
Learn more about Heap in DSA Self Paced Course
Practice Problems on Heap
Top Quizzes on Heap

A Heap is a special Tree-based data structure in which the tree is a complete binary tree.

Heap Data Structure

• Heapify: a process of creating a heap from an array.
• Insertion: process to insert an element in existing heap time complexity O(log N).
• Deletion: deleting the top element of the heap or the highest priority element, and then organizing the heap and returning the element with time complexity O(log N).
• Peek: to check or find the first (or can say the top) element of the heap.

Generally, Heaps can be of two types:

1. 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.
2. 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.

Topics :

Introduction:

1. Introduction to Heap – Data Structure and Algorithm Tutorials
2. Binary Heap
3. Applications, Advantages and Disadvantages of Heap
4. Time Complexity of building a heap
5. Applications of Heap Data Structure
6. Comparison between Heap and Tree
7. When building a Heap, is the structure of Heap unique?

Some other types of Heap:

1. Binomial Heap
2. Fibonacci Heap
3. Leftist Heap
4. K-ary Heap

Standard problems on Heap:

• Easy:
  1. Heap Sort
  2. Check if a given Binary Tree is Heap
  3. How to check if a given array represents a Binary Heap?
  4. Iterative Heap Sort
  5. K’th Largest Element in an array
  6. K’th Smallest/Largest Element in Unsorted Array | Set 1
  7. Height of a complete binary tree (or Heap) with N nodes
  8. Heap Sort for decreasing order using min heap
• Medium:
  1. Sort an almost sorted array
  2. Print all nodes less than a value x in a Min Heap.
  3. Tournament Tree (Winner Tree) and Binary Heap
  4. Connect n ropes with minimum cost
  5. Maximum distinct elements after removing k elements
  6. K maximum sum combinations from two arrays
  7. Median of Stream of Running Integers using STL
  8. Median in a stream of integers (running integers)
  9. K’th largest element in a stream
  10. Largest triplet product in a stream
  11. Find k numbers with most occurrences in the given array
  12. Convert min Heap to max Heap
  13. Given level order traversal of a Binary Tree, check if the Tree is a Min-Heap
• Hard:
  1. Design an efficient data structure for given operations
  2. Merge k sorted arrays | Set 1
  3. Sort numbers stored on different machines
  4. Smallest Derangement of Sequence
  5. Largest Derangement of a Sequence
  6. Maximum difference between two subsets of m elements
  7. Convert BST to Min Heap
  8. Merge two binary Max Heaps
  9. K-th Largest Sum Contiguous Subarray
  10. Minimum product of k integers in an array of positive Integers
  11. Leaf starting point in a Binary Heap data structure
  12. Rearrange characters in a string such that no two adjacent are same
  13. Sum of all elements between k1’th and k2’th smallest elements
  14. Minimum sum of two numbers formed from digits of an array

Quick Links:

• Practice Problems on Heap
• Quizzes on Heap

Recomended:

• Learn Data Structure and Algorithms | DSA Tutorial

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.