---
title: "Heaps"
lastModified: "2026-10-07T11:38:29+05:30"
---

## Overview
Heaps are complete binary trees that satisfy the heap property. They're primarily used to implement priority queues efficiently.

## Characteristics
- **Complete Binary Tree**: Completely filled from left to right
- **Usually implemented as an array** for efficiency
- **Heap Property**:
  - Max-heap: Every node's key ≥ its children's keys
  - Min-heap: Every node's key ≤ its children's keys
- **Weakly ordered** compared to BST (no left-right ordering)
- **Root always contains max (or min) element**

## Operations

### Insertion - O(log n)
1. Place new node at first open position (end of array)
2. Trickle up: Swap with parent if larger (max-heap)
3. Continue until heap property restored

### Removal - O(log n)
1. Remove root (max/min element)
2. Move last node to root
3. Trickle down: Swap with larger child
4. Continue until heap property restored

## Array Representation
- Parent of node at index i: (i-1)/2
- Left child of node at index i: 2*i + 1
- Right child of node at index i: 2*i + 2

## Applications
- **Priority Queues**: Efficient access to highest priority item
- **Heap Sort**: O(n log n) sorting algorithm
- **Dijkstra's Algorithm**: For shortest path
- **Task Scheduling**: In operating systems
- **Huffman Coding**: For data compression

## Heap Sort
1. Build heap from unsorted array
2. Repeatedly remove max element
3. Place removed elements at end of array
- Time Complexity: O(n log n)
- In-place sorting algorithm

## Implementation
- BinaryHeap.java: Max-heap with trickle up/down operations