Question

How Heapify is done (theory, pseudocode, and examples) the examples used Java code please

(in your own words）

Answer 1

HEAP, is a data structure that is a complete binary tree. All the levels are completely filled except for the last level. Heap has some order of values to be maintained between parents and their children.

HEAPSORT is an efficient in-place comparison-based sorting algorithm and uses a data structure to achieve it. It uses a complete Binary Heap data structure to sort the elements depending on whether the heap is Min Heap (ascending) or Max heap (descending).

HEAPIFY method rearranges the elements of an array where the left and right sub-tree of i^th element obeys the heap property.

ALGORITHM

1. Max-Heapify(numbers[], i) 
   leftchild := numbers[2i] 
   rightchild := numbers [2i + 1] 
   if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i] 
      largest := leftchild 
   else 
      largest := i 
   if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest] 
      largest := rightchild 
   if largest ≠ i 
      swap numbers[i] with numbers[largest] 
      Max-Heapify(numbers, largest)

PSEUDOCODE

procedure heapsort(array, n):
     // Step 1: creating the initial Max heap
     for i = n/2 - 1 to 0 do:
         heapify(array, n, i)
     // Step 2: Removing one element and maintaining the heap property
     for i = n-1 to 0 do:
         swap(array[0], array[i])
         heapify(array, i, 0) 
         
procedure heapify(array, n, i)
    // initialize largest as root and get left and right nodes
    int largest = i;
    int left_node = 2*i + 1;
    int right_node = 2*i + 2;
    // Check if left node exists and is larger than root. If yes, change it
    if(left_node < n && arr[left_node] > arr[largest])
        largest = left_node;
    // Check if right node exists and is larger than root. If yes, change it
    if(right_node < n && arr[right_node] > arr[largest])
        largest = right_node;
    // change root, if needed
    if(largest != i)
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);

Example:

Find the kth largest element in the array

Input : 15 35 10 6 17 11

k=3

Output: 15

Java Code:

public class HeapSort {
  
    public void sort(int arr[], int k) {
      int n = arr.length;
  
      for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
      }
  
      for (int i = n - 1; i > k; i--) {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
  
        heapify(arr, i, 0);
      }
      System.out.println(arr[0]);
    }
  
    void heapify(int arr[], int n, int i) {
      int max = i;
      int leftChild = 2 * i + 1;
      int rightChild = 2 * i + 2;
  
      if (leftChild < n && arr[leftChild] > arr[max])
        max = leftChild;
  
      if (rightChild < n && arr[rightChild] > arr[max])
        max = rightChild;
  
      if (max != i) {
        int swap = arr[i];
        arr[i] = arr[max];
        arr[max] = swap;
  
        heapify(arr, n, max);
      }
    }
  
    static void display(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[] = {11, 34, 9, 5, 16, 10};
  
      HeapSort hs = new HeapSort();

          hs.sort(arr,3);

    }
  }