A heap is a specialized tree-based data structure that satisfies the heap property. The heap property is defined differently for min-heaps and max-heaps:

Min-Heap Property: In a min-heap, for any given node C, if P is a parent node of C, then the key (the value) of P must be less than or equal to the key of C. In other words, the smallest element is at the root, and for any given node in the heap, its key is smaller than or equal to the keys of its children.
Max-Heap Property: In a max-heap, for any given node C, if P is a parent node of C, then the key of P must be greater than or equal to the key of C. In this case, the largest element is at the root, and any node's key is greater than or equal to the keys of its children.

Heaps are often used to implement priority queues, where elements with higher (or lower, depending on whether it's a min-heap or max-heap) priority are processed before others. The heap data structure allows for efficient insertion, deletion, and retrieval of the element with the highest (or lowest) priority.

Heaps are typically implemented as binary trees, specifically binary heap trees, because they provide efficient operations and can be efficiently represented using an array. Binary heaps can be categorized into two main types:

Min-Heap: In a min-heap, the root node contains the minimum element, and each parent node has a smaller or equal value compared to its children. This ensures that the minimum element is always at the top, making it efficient to extract the minimum element.
Max-Heap: In a max-heap, the root node contains the maximum element, and each parent node has a greater or equal value compared to its children. This ensures that the maximum element is always at the top, making it efficient to extract the maximum element.

Common operations performed on heaps include:

Insertion: Adding a new element to the heap while maintaining the heap property.
Extraction: Removing and returning the minimum (in a min-heap) or maximum (in a max-heap) element from the heap.
Peek: Returning the minimum (in a min-heap) or maximum (in a max-heap) element without removing it.
Heapify: Rearranging elements in an array to form a valid heap, often used when building a heap from an unsorted array.

Heaps are widely used in algorithms such as heap sort, Dijkstra's shortest path algorithm, and priority queue implementations. They offer efficient solutions to various problems where elements need to be prioritized and processed in a specific order.

Code for implementing heap

Lets write code for Minheap in Javascript:

We are going to write a min heap so that we get the behavior stated beside.
Create class Minheap which has an array called heap in its constructor. This Class has the following functions:
1. push - Function to insert a new element into the heap
2. pop - Function to extract the minimum element from the heap
3. parentIdx - Function to get the index of the parent node
4. heapifyUp - Function to maintain the min-heap property by moving the newly inserted element up
5. heapifyDown - Function to maintain the min-heap property by moving the root element down


const minHeap = new MinHeap();
minHeap.push(4);
minHeap.push(9);
minHeap.push(2);
minHeap.push(1);
minHeap.push(5);
console.log(minHeap.heap); // [1, 2, 4, 9, 5]
console.log(minHeap.pop()); // 1
console.log(minHeap.heap); // [2, 5, 4, 9]

class MinHeap {
  constructor() {
    this.heap = [];
  }
	
	// Function to insert a new element into the heap
  push(value) { }

	// Function to extract the minimum element from the heap
  pop() { }

  // Function to get the index of the parent node
  parentIndex(index) { }

  // Function to maintain the min-heap property by moving the newly inserted element up
  heapifyUp() { }

  // Function to maintain the min-heap property by moving the root element down
  heapifyDown() { }

}

Code for implementing heap

Problems using Heaps

Easy

Medium

Hard