Heap Sort Algorithm Explained: A Beginner Friendly Guide with Leetcode Solutions In Java

When it comes to sorting algorithms, heap sort is one of the most efficient and reliable options. In this article, we’ll take a deep dive into heap sort, explaining every step in a simple and beginner-friendly manner. We’ll also provide Java code examples from Leetcode to make the concepts more practical and understandable.

Table of Contents

What is Heap Sort?

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. A binary heap is a complete binary tree where each parent node is either greater than or equal to its child nodes (in a max heap), or less than or equal to its child nodes (in a min heap).

Heap sort works by first building a max heap from the input data, and then repeatedly extracting the maximum element from the heap and placing it at the end of the array.

Advantages of Heap Sort

Time Complexity: O(n log n) for all cases (best, average, worst)
Space Complexity: O(1), since it’s an in-place sorting algorithm
Efficient for Large Data Sets

Disadvantages of Heap Sort

Not Stable: The relative order of equal elements may not be preserved.

Understanding the Heap Data Structure

A binary heap can be visualized as a binary tree but is implemented as an array. The key property is:

For a node at index i, its left child is at index 2 * i + 1, and the right child is at 2 * i + 2.

In a max heap, the value of each parent is greater than or equal to that of its children.

Heap Sort Algorithm: Step-by-Step Approach

Let’s break down the heap sort algorithm into two major phases:

Step 1: Build a Max Heap

We rearrange the array elements to satisfy the max heap property. We start from the last non-leaf node and apply heapify in reverse level order.

Step 2: Extract Elements from Heap One by One

After building the heap:

Swap the root element (largest) with the last element.
Reduce the size of the heap by one.
Heapify the root element again to maintain the max heap property.
Repeat until the heap is reduced to a single element.

Java Code for Heap Sort

public class HeapSort {

    public void sort(int arr[]) {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // One by one extract elements from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    void heapify(int arr[], int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest])
            largest = left;

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    // Utility function to print array
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        HeapSort ob = new HeapSort();
        ob.sort(arr);

        System.out.println("Sorted array is");
        printArray(arr);
    }
}

Also check: Greedy Algorithm: A Comprehensive Guide With Examples

Step-by-Step Example

Let’s walk through an example to clarify how heap sort works.

Input Array: [12, 11, 13, 5, 6, 7]

For the above example, here’s a visual representation of how the algorithm works. Click the arrows to view the steps.

Build Max Heap

Start from the last non-leaf node: index 2 (value 13) and apply heapify backwards:

heapify at index 2: [12, 11, 13, 5, 6, 7]
heapify at index 1: [12, 11, 13, 5, 6, 7]
heapify at index 0: [13, 11, 12, 5, 6, 7]

Extract Elements

Swap 13 with 7: [7, 11, 12, 5, 6, 13]
Heapify root: [12, 11, 7, 5, 6, 13]
Swap 12 with 6: [6, 11, 7, 5, 12, 13]
Heapify root: [11, 6, 7, 5, 12, 13]
Continue this until sorted: [5, 6, 7, 11, 12, 13]

Coding Problems Solved Using Heap Sort

Problem 1: Find the Kth Largest Element in an Array – Heap Sort Solution

Problem: Given an unsorted array, find the kth largest element..

Leetcode Problem: Kth Largest Element in an Array

Approach: Min-Heap of Size k

Maintain a min-heap (priority queue) of size k.
Iterate through each element:
- Add the element to the min-heap.
- If the heap size exceeds k, remove the smallest element.
At the end, the root of the min-heap will be the kth largest element.

Java Code Using Heap Sort:

import java.util.PriorityQueue;

public class KthLargestElement {

    public static int findKthLargest(int[] nums, int k) {
        // Min-heap to keep track of k largest elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll();  // Remove smallest element
            }
        }

        // The root of the heap is the kth largest element
        return minHeap.peek();
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;

        int kthLargest = findKthLargest(nums, k);
        System.out.println(k + "th largest element is: " + kthLargest);
        // Output: 2th largest element is: 5
    }
}

Explanation:

The min-heap keeps the k largest elements seen so far.
When the heap size exceeds k, the smallest element is removed, ensuring only the k largest remain.
The smallest element in the heap (heap root) after processing all elements is the kth largest in the entire array.

Time & Space Complexity:

Time Complexity: O(n log k), where n = number of elements
- Each insertion/removal in the heap takes O(log k) time.
Space Complexity: O(k), heap stores k elements.

Problem 2: Top K Frequent Elements – Heap Sort Solution

Leetcode Problem: Top K Frequent Elements

Problem: Given an integer array nums and an integer k, return the k most frequent elements.in sorted order.

Approach:

Count Frequencies: Use a HashMap to count how many times each number appears.
Maintain a Min-Heap of Size K: Push (num, frequency) pairs into the min-heap. If heap size exceeds k, remove the element with the lowest frequency.
Extract Elements from Heap: The remaining k elements in the heap are the top k frequent.

Java Code Using Heap Sort:

import java.util.*;

public class TopKFrequentElements {

    public static int[] topKFrequent(int[] nums, int k) {
        // Step 1: Count frequency of each element
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Use min-heap to keep top k frequent elements
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = 
            new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());

        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            minHeap.add(entry);
            if (minHeap.size() > k) {
                minHeap.poll(); // remove least frequent
            }
        }

        // Step 3: Build result from heap
        int[] result = new int[k];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : minHeap) {
            result[index++] = entry.getKey();
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;

        int[] result = topKFrequent(nums, k);
        System.out.println("Top " + k + " frequent elements: " + Arrays.toString(result));
        // Output: Top 2 frequent elements: [1, 2]
    }
}

Explanation:

The min-heap keeps the top k most frequent elements seen so far.
When the heap size exceeds k, the element with the lowest frequency is removed — ensuring only the k most frequent remain.
After processing all elements, the heap contains the k elements with the highest frequencies.
We extract the keys (numbers) from the heap to get the final result.

Time & Space Complexity:

Time Complexity: O(n log k)
- O(n) for counting frequencies
- O(n log k) for inserting into heap
Space Complexity: O(n)
- For the hash map and heap

Also check: Backtracking Algorithm Explained With Examples

Problem 3: Merge K Sorted Lists – Heap Sort Solution

Problem: Merge k sorted lists into one sorted list.

Leetcode Problem: Merge K Sorted Lists

Input: An array of k sorted linked lists
Output: A single sorted linked list containing all elements from the input lists

Approach:

Use a min-heap (PriorityQueue) to efficiently get the smallest current node across all lists.
Insert the head node of each list into the heap.
Repeatedly extract the smallest node and add it to the result list.
If the extracted node has a next node, insert it into the heap.

This mimics a heap sort behavior by always maintaining the smallest current item at the top of the heap.

Java Code Using Heap Sort:

import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class MergeKSortedLists {

    public ListNode mergeKLists(ListNode[] lists) {
        // Min-heap based on node value
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> a.val - b.val
        );

        // Initialize heap with the head of each list
        for (ListNode list : lists) {
            if (list != null)
                minHeap.add(list);
        }

        // Dummy head for the result list
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Extract min and push next nodes into the heap
        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            current.next = node;
            current = current.next;

            if (node.next != null)
                minHeap.add(node.next);
        }

        return dummy.next;
    }

    // Helper to print the linked list
    public void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    // Example usage
    public static void main(String[] args) {
        MergeKSortedLists merger = new MergeKSortedLists();

        // Example: [[1->4->5], [1->3->4], [2->6]]
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        ListNode l3 = new ListNode(2);
        l3.next = new ListNode(6);

        ListNode[] lists = {l1, l2, l3};

        ListNode result = merger.mergeKLists(lists);
        merger.printList(result);  // Output: 1 1 2 3 4 4 5 6
    }
}

Explanation:

Initialize a Min-Heap (Priority Queue): We create a min-heap that will always keep track of the smallest current node among all the heads of the k lists.
Insert the Head Nodes of All Lists into the Heap: Each of the k lists has a starting node (head). We add these head nodes into the min-heap.
Build the Result List by Extracting the Smallest Node:
- Extract the smallest node from the heap (this is the smallest among all current heads).
- Add this node to the merged result list.
- If the extracted node has a next node, insert that next node into the heap.
Repeat Until the Heap is Empty: Keep extracting the smallest node and adding the next nodes from the original lists until all nodes are merged.

Time & Space Complexity:

Time Complexity: O(N log k)
- N = total number of nodes
- k = number of linked lists
- Each insertion/extraction in heap takes O(log k)

Space Complexity: O(k) for the heap

Conclusion

Heap sort is a powerful and space-efficient sorting algorithm that guarantees O(n log n) time performance. Although it’s not stable, its in-place sorting mechanism makes it suitable for systems with limited memory.

Beyond sorting, the heap data structure is incredibly versatile and can be applied to solve a wide range of problems such as k-sorted arrays, finding the k-largest elements, and merging k-sorted arrays.

With the step-by-step breakdown, Java implementations, and real-world coding problems provided in this guide, beginners can easily understand, practice, and apply heap sort in various programming challenges.

Continue practicing and experimenting with the algorithm using various datasets to thoroughly master the concept.

That’s all on the Heap Sort algorithm.

To keep yourself up to date with our latest content, please subscribe to our newsletter by dropping your email address here: Signup for Our Newsletter.

Please follow us on Medium.