Implementing Binary Heaps with Arrays

1. What is a Binary Heap?

A binary heap is a binary tree that satisfies two specific properties. Understanding these properties is the key to implementing the structure correctly.

1. Structure Property: A Complete Binary Tree
   A heap must be a complete binary tree. This means all levels of the tree are filled, except possibly the last level, which is filled from left to right without any gaps.

2. Heap Property: Min-Heap or Max-Heap
   This property defines the relationship between a parent and its children.

   • Min-Heap: The value of any node is less than or equal to the values of its children. This ensures the smallest element is always at the root of the tree.
   • Max-Heap: The value of any node is greater than or equal to the values of its children. This ensures the largest element is always at the root.

To solidify these concepts, let's watch a short, clear explanation.

This structure is what makes heaps so efficient for their intended purpose. The ability to find the min or max element in $O(1)$ time is a direct consequence of the heap property. This makes them the ideal data structure for implementing Priority Queues, where you always need to process the item with the highest (or lowest) priority first.

2. The Array-Based Representation

Although we visualize heaps as trees, their "complete" nature makes them perfectly suited for implementation using a simple array (or an ArrayList in Java). We don't need Node objects with left and right pointers.

How does this work? We store the tree elements level by level, from left to right, in an array.

Given a node at index i in a 0-indexed array:

• Its parent is at index (i - 1) / 2.
• Its left child is at index 2 * i + 1.
• Its right child is at index 2 * i + 2.

These simple formulas allow us to navigate the tree structure using array indices alone, which is highly efficient.

3. Implementing Heap Operations

Now for the core of the lesson: implementing the main operations. We'll focus on a min-heap first. The logic for a max-heap is nearly identical, just with the comparisons flipped.

The two main operations are insert and extractMin (removing the root). The challenge is to perform these operations while maintaining both the structure and heap properties. This is done through two helper processes often called "bubbling" or "percolating".

3.1 Insertion and percolateUp

To insert a new element into a min-heap:

1. Add to the end: Place the new element at the first available spot in the array. This maintains the complete binary tree structure.
2. Fix the heap property: The new element might be smaller than its parent, violating the min-heap property. To fix this, we "percolate up" (or "bubble up"). We compare the new element with its parent and swap them if they are in the wrong order. We repeat this process, moving the element up the tree until it's in its correct position (i.e., its parent is smaller than it, or it has reached the root).

This process ensures the operation takes $O(\log N)$ time, as the height of a complete binary tree with N nodes is $\log N$.

Let's see a dry run of this upheap process.

Now that you've seen the logic, let's look at a clean Java implementation.

3.2 extractMin and percolateDown

Extracting the minimum element from a min-heap always means removing the root.

1. Save the root: The root (array[0]) is the minimum element. Store it to return later.
2. Move last element to root: Take the last element in the heap and place it at the root position. Then, shrink the heap size by one. This is a clever trick to maintain the complete tree structure.
3. Fix the heap property: The new root is likely larger than one or both of its children, violating the min-heap property. To fix this, we "percolate down" (or "bubble down"). We compare the node with its children, find the smaller of the two children, and if that child is smaller than the current node, we swap them. We repeat this process, moving the element down the tree until it's in its correct position.

This operation also has a time complexity of $O(\log N)$.

Let's watch a dry run of this downheap process.

Now, let's examine the corresponding Java code.

3.3 Implementing a Max-Heap

Implementing a max-heap is straightforward once you have a min-heap. You simply flip every comparison:

• In percolateUp, you swap if child > parent.
• In percolateDown, you swap with the larger child if child > parent.

4. Complete Heap Implementation in Java

Now let's put all the pieces together into a single, generic Heap class. The following resource provides a full code-along that creates a generic heap implementation from scratch, which is excellent practice for your interview preparation.

Conclusion

Great job! You've just learned how to implement one of the most useful data structures in computer science. By representing a complete binary tree with an array and using clever "percolating" algorithms, we can build a highly efficient structure for priority-based problems.

Key Takeaways:

• A Binary Heap is a complete binary tree that satisfies the min-heap or max-heap property.
• It can be efficiently implemented using an array by calculating parent/child relationships with index arithmetic: parent = (i-1)/2, leftChild = 2*i+1, rightChild = 2*i+2.
• Insertion involves adding an element to the end of the array and calling percolateUp to restore the heap property. Complexity: $O(\log N)$.
• Extraction (of min/max) involves replacing the root with the last element, shrinking the array, and calling percolateDown on the new root. Complexity: $O(\log N)$.
• A max-heap implementation is identical to a min-heap, with all comparisons reversed.

Preview of the Next Lesson:
We learned how to build a heap by inserting elements one by one. But what if you are given a whole collection of items at once? In the next lesson, we will explore a more efficient method to build a heap from an unordered array in linear $O(N)$ time. This "heapify" algorithm is a classic and powerful technique. After that, we'll be ready to implement Heap Sort