
Heap is a complete binary tree structure where each node satisfies a heap property. We learn two types of heap data structure: 1) Max heap, which satisfies the max heap property, and 2) Min heap, which satisfies the min-heap property. We use heap data structures to implement priority queues and solve several coding problems efficiently.

Given an array and a positive integer k, write a program to find the kth smallest element in the array. This is an excellent problem to learn problem-solving using the max and min heap data structures. The quick-select approach (divide and conquer) is also worth exploring because it helps to optimize time complexity to O(n) on average.

Before performing any max or min heap operations, we need to build a max or min heap from the given array. The critical questions are: How do we achieve this? How do we maintain the heap structure and heap property at each element in the array? In this blog, we will discuss answers to these questions.

We use the heapify operation to fix the violation of heap property at a given node in the heap. Such violations actually happen due to several reasons: 1) After inserting a new element in the heap 2) After removing the max element in a max heap or min element in the max heap 3) After updating some value with the new value.