Binary Heap Data Structure - Java Code

A nearly complete binary tree, where parent node has a priority over child nodes.

Two types:

• Max heap
• The key of parent nodes is always greater than or equal to those of the children
• Thus, the maximum key is in the root node
• Min heap
• The key of parent node is always less than or equal to those of the children
• Thus, the minimum key is in the root node

Heap as an array: Building a heap : O(n) time complexity

Root is at index = 0: 

Root of the tree = first element ( i = 0 )

Parent ( i ) = (i – 1)/ 2

Left( i ) = 2*i + 1

       Right( i ) = 2*i + 2

Root is at index = 1: 

Root of the tree = first element ( i = 1 )

Parent ( i ) = i / 2

Left( i ) = 2*i

       Right( i ) = 2*i + 1

Algorithm

Algorithm Build-Max-Heap (A):
       Input: An unsorted array A

       Output: Heap structured array A

n ← length ( A )

# the parent of the last element is at index [n/2 -1] 

for i ← n/2 - 1 downto 0 do

Max-Heapify (A, i)

--------------------------------------------------------------------

Algorithm Max-Heapify (A, i):
       Input: An unsorted array A

       Output: The subtree with root node i is in heap structure

       Precondition: The subtrees left(i) and right(i) are already in heap structure

n ← length ( A )

left ← 2*i + 1

right ← 2*i + 2

largest ← i

if left < n and A[left] > A[largest] then:
    largest ← left

if right < n and A[right] > A[largest] then:
    largest ← right

 if i ≠ largest  then:
    swap A[i] ↔ A[largest]
    Max-Heapify(A, largest)

Java Code

import java.util.Arrays;

public class Heap {

       public void buildMaxHeap(int[] arr) {

              int n = arr.length;

              for (int i = (n / 2 - 1); i >= 0; i--) {

                     maxHeapify(arr, i);

              }

       }

       private void maxHeapify(int[] arr, int i) {

              int left = 2 * i + 1;

              int right = 2 * i + 2;

              int largest = i;

              if (left < arr.length && arr[left] > arr[largest]) {

                     largest = left;

              }

              if (right < arr.length && arr[right] > arr[largest]) {

                     largest = right;

              }

              if (i != largest) {

                     swap(arr, i, largest);

                     maxHeapify(arr, largest);

              }

       }

       private void swap(int[] arr, int i, int j) {

              int temp = arr[i];

              arr[i] = arr[j];

              arr[j] = temp;

       }

       public static void main(String[] args) {

              int[] arr = { 10, 80, 40, 30, 0, 70, 110, 10, 150, 20, 90, 60, 50, 120, 140, 130 };

              Heap heap = new Heap();

              heap.buildMaxHeap(arr);

              System.out.println(Arrays.toString(arr));

       }

}