Important Interview Questions of Heap Data Structure
1. What is Heap Data Structure?
Heap is a special tree-based data structure in which the tree is a complete binary tree. It satisfies the heap property.It is also called as a binary heap.
Heap property:
In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the value of C.
In a min heap, the value of P is less than or equal to the value of C. The node at the “top” of the heap (with no parents) is called the root node.
Generally, Heaps can be of two types: Max Heap or Min Heap.
2. What is the time complexity of Build Heap operation.
Build Heap operation is a Linear Time Operation, O(n). It is used to build either max or min heap. Build heap is first step in Heap Sort technique ( O(nlogn).
3. Can you write a quick algo to build heap from an array.
4. What are conditions of max heap? Which of the following is a max-heap?
Conditions of Heap:
- Heap order property (either max or min heap ): Value of each parent is greater than or equal to the values of its children.
- CBT Property: It should follow complete binary tree ( CBT ) property i.e each level must be completely filled, except last level that can be partially filled from left to right.
- It is a Binary Tree.
Option B is correct.
5. Discuss complexity of all heap operations.
6. Find kth largest element in an array. Amazon
7. Find median of running stream of integers. Google| Paytm
8. Write complexity of each step of Heap Sort.
9. Explain all steps of Heap Sort Algorithm.
Step 1: Build Max Heap, it takes linear time 0(n)
Step 2: Swap the first and last numbers, it takes constant time 0(1)
Step 3: Shrink the heap size
Step 4: Max Heapify the first index, it takes linear time 0(logn)
Understand heap sort through lecture.
10. What is Priority Queue?
A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority.
Example: Queue of people in front of a Bank arranged in a specific order (of age). Old people of greater age are asked to come ahead in the line.
11. What is difference between Normal Queue and Priority Queue?
In a queue, the first-in-first-out rule is implemented whereas, in a priority queue, the values are removed on the basis of priority. The element with the highest priority is removed first.
12. How to implement Priority Queue?
Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list.
13. Syntax of Priority Queue in C++ STL?
14. What are applications of heap data structure?
Heap data structures are significantly used for heap sort (an inplace sorting algorithm). Apart from sorting these are used in following ways:
- Priority Queue- Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time.
- Order statistics- The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.
15. Must Do: Connect N ropes with minimum cost- Amazon | Goldman Sachs
16. Merge K sorted Arrays- Facebook | Google
Do clap 👏🏻👏🏻 50 times and share the article if you like it. Thank you for giving your valuable time
