Heap

Introduction

A heap is a complete binary tree-based data structure that efficiently maintains a specific order property, making it ideal for scenarios where quick access to the highest or lowest priority element is required. It is a complete binary tree, meaning all levels are fully filled except possibly for the last level, which is filled from left to right.

Heaps are commonly used to implement priority queues, where elements are inserted with an associated priority, and the highest (or lowest) priority element can be quickly retrieved. The heap structure allows for efficient operations like insertion, deletion, and peek (retrieving the top element) in logarithmic time, which is much faster than linear-time alternatives like arrays or linked lists.

A heap is a complete binary tree that satisfies a specific heap property, and it can either be a min-heap or a max-heap.

• In a Min-Heap, the value of each parent node is less than or equal to the values of its children, ensuring that the smallest element is always at the root.
• In a Max-Heap, the value of each parent node is greater than or equal to the values of its children, ensuring that the largest element is always at the root.

Binary Heap Representation in an Array

• The root of the heap is at index 0.

For a node at index i:

• The left child is at index 2i + 1.

• The right child is at index 2i + 2.

• The parent of the node is at index (i - 1) / 2.