Heaps Overview

In many computer science applications, we only need to access the largest or smallest element in the dataset. We do not care about the order of other data in the data set. How do we efficiently access the largest or smallest element in the current dataset? The answer would be Heap.

After reading this section, you will,

• Have a better understanding of the “Heap” data structure and its implementation;

• Have a better understanding of the concepts and methods of Max Heap and Min Heap;

• Have a better understanding of Heap Sort;

• Have a better understanding of the application scenarios of “Heap”;

• Be able to use “Heap” in practice.

A priority queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.

A Heap is not a Priority Queue, but a way to implement a Priority Queue.

There are multiple ways to implement a Priority Queue, such as array and linked list. However, these implementations only guarantee O(1) time complexity for either insertion or deletion, while the other operation will have a time complexity of �(O(N). On the other hand, implementing the priority queue with Heap will allow both insertion and deletion to have a time complexity ofO(logN)

A heap is a binary tree that meets the following criteria:

• Is a complete binary tree;

• The value of each node must be no greater than (or no less than) the value of its child nodes.

A Heap has the following properties:

• Insertion of an element into the Heap has a time complexity of O(logN);

• Deletion of an element from the Heap has a time complexity of O(logN);

• The maximum/minimum value in the Heap can be obtained with O(1) time complexity.

There are two kinds of heaps:

• Max Heap (Top element is largest)

• Min Heap. (Top element is smallest)

Heap Construction in Java & why heap contruction is O(N)

Heapify means converting a group of data into a Heap.

What’s the time complexity of building a heap? The first answer that comes to my mind is O(n log n). But due to complete binary tree structure height will be lesser than the n. So time complexity reduce to O(N)

Time complexity: O(N).

Space complexity: O(N).

// In Java, a Heap is represented by a Priority Queue
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Arrays;
// Construct an empty Min Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Construct an empty Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// Construct a Heap with initial elements. 
// This process is named "Heapify".
// The Heap is a Min Heap
PriorityQueue<Integer> heapWithValues= new PriorityQueue<>(Arrays.asList(3, 1, 2));

Inserting into Heap

Time complexity: O(logN)

Space complexity: O(1)

Get Top Elements

Time complexity: O(1).

Space complexity: O(1).

// Get top element from the Min Heap
// i.e. the smallest element
minHeap.peek();
// Get top element from the Max Heap
// i.e. the largest element
maxHeap.peek();

Deleting Element

Time complexity: O(logN).

Space complexity: O(1).

Getting the Length of a Heap

Time complexity: O(1)

Space complexity: O(1)

// Length of the Min Heap
minHeap.size();
// Length of the Max Heap
maxHeap.size();
// Note, in Java, apart from checking if the length of the Heap is 0, we can also use isEmpty()
// If there are no elements in the Heap, isEmpty() will return true;
// If there are still elements in the Heap, isEmpty() will return false;

why getting the size of heap is O(1). There is size variable, when we add element size will be incremented.

Complete Code

// Code for Min Heap
import java.util.PriorityQueue;

public class App {
    public static void main(String[] args) {
        // Construct an instance of Min Heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Add 3，1，2 respectively to the Min Heap
        minHeap.add(3);
        minHeap.add(1);
        minHeap.add(2);

        // Check all elements in the Min Heap, the result is [1, 3, 2]
        System.out.println("minHeap: " + minHeap.toString());

        // Get the top element of the Min Heap
        int peekNum = minHeap.peek();

        // The result is 1
        System.out.println("peek number: " + peekNum);

        // Delete the top element in the Min Heap
        int pollNum = minHeap.poll();

        // The reult is 1
        System.out.println("poll number: " + pollNum);

        // Check the top element after deleting 1, the result is 2
        System.out.println("peek number: " + minHeap.peek());

        // Check all elements in the Min Heap, the result is [2,3]
        System.out.println("minHeap: " + minHeap.toString());

        // Check the number of elements in the Min Heap
        // Which is also the length of the Min Heap
        int heapSize = minHeap.size();

        // The result is 2
        System.out.println("minHeap size: " + heapSize);

        // Check if the Min Heap is empty
        boolean isEmpty = minHeap.isEmpty();

        // The result is false
        System.out.println("isEmpty: " + isEmpty);
    }
}

Application of Heap

Heap Sort

Time complexity : O(N logN)

        int arr[] = new int[] {1,5,2,8,3,9,1,20};

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int n : arr) {
            queue.add(n);
        }

        while (!queue.isEmpty()) {
            System.out.println(queue.peek());
            queue.poll();
        }

Get the Top K Elements of an array

Approach 1: Heapify elements and get top K

Complexity Analysis:

Time complexity: O(K logN+N)

• construct a Max Heap which requires O(N) time

• Each element removed from the heap requires O(log N) time. this process is repeated K times.

• Thus the total time complexity is O(K logN+N).

Space complexity: O(N)

Approach 2 :

• Construct a Min Heap with size K.

• Add elements to the Min Heap one by one.

• When there are K elements in the “Min Heap”, compare the current element with the top element of the Heap:

• If the current element is no larger than the top element of the Heap, drop it and - proceed to the next element.

• If the current element is larger than the Heap’s top element, delete the Heap’s top element, and add the current element to the Min Heap.

• Repeat Steps 2 and 3 until all elements have been iterated.

        int arr[] = new int[] {1,5,2,8,3,9,1,20};
        //Find the Top K elements
        System.out.println("Finding top k elements");
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int K = 4;

        for(int i=0 ; i < K ;i++) {
            queue.add(arr[i]);
        }

        for(int i=K ; i< arr.length;i++) {
            if (arr[i] > queue.peek() ) {
                queue.poll();
                queue.add(arr[i]);
            }
        }
        while (!queue.isEmpty()) {
            System.out.println(queue.peek());
            queue.poll();
        }
        System.out.println("===================");

Get K Least Elements in array

Same as above but construct with max heap

 PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

Find Kth Largest Element or Kth Smallest Element in the array

Same as above problem Get the Top K Elements of an array

public int findKthLargest(int[] nums, int k) {

        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int i=0 ; i < k ;i++) {
            q.add(nums[i]);
        }
        for(int i=k ; i< nums.length;i++) {
            if (nums[i] > q.peek()) {
                q.poll();
                q.add(nums[i]);
            }
        }
        return q.peek();
    }