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));

       }

}

Kth Smallest Element in a BST - Java Code

To calculate the k^th smallest element, we use the following property of a BST that is:

• The left sub-tree of a node T contains the nodes whose keys ( values ) are less than that of the current node T.
• The right sub-tree of a node T contains the nodes whose keys ( values ) are greater than that of the current node T.

So, based on the above two properties, we can think of the following algorithm to find out kth smallest element.

Algorithm

For a node T,

• If k = num_nodes(left Subtree of T) + 1, then the answer is the value in node T
• If k < num_nodes(left Subtree of T) + 1, then the k^th smallest is in the left sub-tree, so we reduce the problem to finding the k^th smallest element in the left subtree.
• If k > num_nodes(left Subtree of T) + 1, then the k^th smallest is in the right sub-tree, So, we reduce the problem to finding the { k - num_nodes(left subtree of T) - 1 } smallest element of the right subtree.

Java Code

class TreeNode {

       int val;

       TreeNode left;

       TreeNode right;

       TreeNode(int x) {

              val = x;

       }

}

public int kthSmallest(TreeNode root, int k) {

       int leftSubtreeCount = getNoOfNodes(root.left) + 1; // one for the current node

       if (k == leftSubtreeCount) {

              return root.val;

       } else if (k < leftSubtreeCount) {

              return kthSmallest(root.left, k);

       } else {

              return kthSmallest(root.right, k - leftSubtreeCount);

       }

}

private int getNoOfNodes(TreeNode currentNode) {

       if (currentNode == null) {

              return 0;

       }

       return 1 + getNoOfNodes(currentNode.left)

                     + getNoOfNodes(currentNode.right);

}

Radix Sort - Java Code

A non-comparative sorting algorithm

• Key Idea: Sort the Least Significant Digit first
• Worst case time complexity: O( wn ), where w = no. of digits, n = no. of keys

Algorithm

Algorithm RadixSort(A)

       Input: An integer array A

       Output: A sorted array A

d ← no. of digits of maximum number of A

for i = 1 to d do

Any stable sort on A based on the digit i (Usually counting sort)

Java Code

public void radixSort(int[] arr) {

       // Getting maximum item for the number of digits required to sort

       int maxItem = getMaximumItem(arr);

       int noOfDigits = String.valueOf(maxItem).length();

       for (int digit = 1; digit <= noOfDigits; digit++) {

              countSort(arr, digit);

       }

}

public void countSort(int arr[], int digit) {

       int divisor = (int) Math.pow(10, digit - 1);

       int[] count = new int[10];

       // Storing the occurrences/frequencies of the items

       for (int i = 0; i < arr.length; i++) {

              int itemDigit = (arr[i] / divisor) % 10;

              count[itemDigit]++;

       }

       // Storing the cumulative frequencies

       for (int i = 1; i < 10; i++) {

              count[i] += count[i - 1];

       }

       // Build the sorted array based on the current digit

       int[] sortedArray = new int[arr.length];

       for (int i = arr.length - 1; i >= 0; i--) {

              int itemDigit = (arr[i] / divisor) % 10;

              sortedArray[count[itemDigit] - 1] = arr[i];

              count[itemDigit]--;

       }

       // Copying the sorted array to the original array

       for (int i = 0; i < arr.length; i++) {

              arr[i] = sortedArray[i];

       }

}

public int getMaximumItem(int arr[]) {

       int maxItem = arr[0];

       for (int i = 1; i < arr.length; i++) {

              if (arr[i] > maxItem) {

                     maxItem = arr[i];

              }

       }

       return maxItem;

}