# Learn Heap Data-Structure in Easiest Way

Heap is a special Tree based Data-Structure in which the tree is a complete binary tree.

It is generally of two types -

* Max-heap - where the root node must be greatest among all its child nodes and the same goes for its right subtree and left subtree.
    
* Min-heap - where the root node must be smallest among all its child nodes and the same goes for its right subtree and left subtree.
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1671804396391/de80f8b0-3d71-479f-98b5-efcec23d05b0.png align="center")
    

## Operations on a Heap -

* insert() - Inserts data into Heap.
    
* extract min() - Extracts and deletes the smallest element in the Heap while maintaining its properties.
    
* decreaseKey() - Changes an element at an index in the Heap while maintaining its properties.
    
* deleteKey() - Deletes an element at an index in the Heap while maintaining its properties.
    
* heapify() - The process of creating a heap data structure from a binary tree represented using an array.
    
* buildHeap() - converts an array into a Heap using the help of heapify function.
    
* getMin()/getMax() - Returns the minimum/maximum element of the Heap.
    

## Implementation of Heap -

Heap is represented using arrays where the element at the 0-th index is greatest in the case of a Max-heap and minimum in the case of a Min-heap.

We find the right and left child using the formula -

* left child = 2\*i+1
    
* right child = 2\*i+2
    
* parent = (i-1)/2
    
* Here, i is the index of the node.
    

```cpp
#include <iostream>
using namespace std;

class Heap
{
    int size;
    int capacity;
    int arr[];
    Heap(int c)
    {
        size = 0;
        capacity = c;
        arr = new int[c];
    }
    int leftChild(int i) // extracts left child Index
    {
        return (2 * i + 1);
    }
    int rightChild(int i) // extracts right child index
    {
        return (2 * i + 2);
    }
    int parent(int i) // extracts parent index of a node
    {
        return (i - 1) / 2;
    }
    insert(int x) // Time Complexity o(logn) // inserts in Heap
    {
        if (size == capacity)
            return;
        size++;
        arr[size - 1] = x;
        int i = size - 1;
        while (i != 0 && arr[parent(i)] > arr[i])
        {
            swap(arr[parent(i)], arr[i]);
            i = parent(i);
        }
    }
    void minHeapify(int i) { // Time Complexity O(logN)
        int li = leftChild(i), ri = rightChild(i);
        int smallest = i;
        if (li < size && arr[li] < arr[smallest])
        {
            smallest = li;
        }
        if (ri < size && arr[ri] < arr[smallest])
        {
            smallest = ri;
        }
        if (smallest != i)
        {
            swap(arr[i], arr[smallest]);
            minHeapify(smallest);
        }
    }
    int getMin() // extracts minimum element from heap
    {
        return arr[0];
    }

    int extractMin()//removes minimum element from heap and returns it
    {
        if (size == 0)
            return INT_MAX;
        if (size == 1)
        {
            size--;
            return arr[0];
        }
        swap(arr[0], arr[size - 1]);
        size--;
        minHeapify(0);
        return arr[size];
    }
    void decreaseKey(int i, int x) //changes a heap element at index i
    {
        arr[i] = x;
        while (i != 0 && arr[parent(i)] > arr[i])
        {
            swap(arr[parent(i)], arr[i]);
            i = parent(i);
        }
    }

    void deleteKey(int i) // deletes a element at i index
    {
        decreaseKey(i, INT_MIN);
        extractMin();
    }

    void buildHeap() // T.C. O(N) //builds the heap using heapify()
    {
        for (int i = (size - 2) / 2; i >= 0; i--)
        {
            minHeapify(i);
        }
    }
}
```

## Applications of Heap -

* Heap is used to constructing a priority\_queue
    
* Heap sort is the fastest sorting algorithm with time complexity O(N\*logN) and is easy to implement.
    

## priority\_queue -

In c++, the STL priority\_queue provides the functionality of the priority queue which is internally created using Heap Data-Structure.

To solve questions related to Heap priority\_queue will be used in c++, it is of two types ascending priority queue and descending priority queue.

To create a min heap the syntax is -

* priority\_queue&lt;int,vector&lt;int&gt;,greater&lt;int&gt;&gt; pq;
    

To create a max heap the syntax is -

* priority\_queue&lt;int&gt; pq;
    

### priority\_queue functions -

* size() - returns the size of the queue
    
* push() - pushes an element inside the queue
    
* pop() - deletes the first element of the queue
    
* empty() - checks whether the queue is empty or not
    
* top() - returns a topmost element of the queue
    

## Heap Interview Questions -

* [Heap implementation](https://github.com/ratishjain12/DSA/blob/main/Heaps/implementation/heap.cpp)
    
* [Check if an array is a heap or not](https://github.com/ratishjain12/DSA/blob/main/Heaps/checkif-arr-is-heap-or-not.cpp)
    
* [Convert a min-heap to max-heap](https://github.com/ratishjain12/DSA/blob/main/Heaps/convert-minheap-to-max.cpp)
    
* [Heap sort](https://github.com/ratishjain12/DSA/blob/main/Heaps/heap-sort.cpp)
    
* [K-closest](https://github.com/ratishjain12/DSA/blob/main/Heaps/k-closest.cpp)
    
* [K-frequent numbers](https://github.com/ratishjain12/DSA/blob/main/Heaps/k-frequent-numbers.cpp)
    
* [K-th largest/smallest element](https://github.com/ratishjain12/DSA/blob/main/Heaps/kthlargestelement.cpp)
    
* [Merge-k-sorted arrays](https://github.com/ratishjain12/DSA/blob/main/Heaps/merge-k-sorted-arr.cpp)
    
* [The minimum cost of the rope](https://github.com/ratishjain12/DSA/blob/main/Heaps/minimcostofrope.cpp)
    
* [Sort k-sorted array(nearly sorted)](https://github.com/ratishjain12/DSA/blob/main/Heaps/sort-k-sorted(nearly%20sorted).cpp)
    

## A resource to get in-depth knowledge -

%[https://www.youtube.com/watch?v=-VhasEYfeT0&list=PLzjZaW71kMwTF8ZcUwm9md_3MvtOfwGow] 

Congrats! you have learned the fundamentals of Heap Data-Structure, make sure to subscribe to my blog to follow this series and follow me on Hashnode, where I'll be uploading content on Data Structures and Algorithms every weekend.