Heap Sort Algorithm in Java

[10446 views]




Heap as a tree:

An array can be visualized as a nearly complete binary tree.
Heap as a tree in Heap Sort Algorithm or Pseudocode Implemented in Java
Properties of this tree:
  • Root of the tree : First element of the array
  • Parent of element at index i : element at index i/2
  • left child of element at index i : element at index 2*i
  • Right child of element at index i : element at index 2*i+1

Max heap:

In max heap, the parent's value is higher than both of its children.

Heap Operations:

  1. Build_max_heap: Produces a max heap from an unordered array
  2. max_heapify: Correct a single violation of the heap property in a subtree's root

Heap Sort algorithm steps:

  1. Build max-heap from unordered array
  2. Find max element in Array A, A[n]
  3. Swap this element A[n] from A[1], now max element is at the end of array
  4. Now discard the node 'n' from the heap by decrementing heap size
  5. New root may violate the max heap property, but children are max heaps, so run max heapify to fix

Heap Sort Pseudocode Implementation in Java:

public class HeapSort { private static int N; public static void sort(int arr[]){ heapify(arr); for (int i = N; i > 0; i--){ swap(arr,0, i); N = N-1; maxheap(arr, 0); } } public static void heapify(int arr[]){ N = arr.length-1; for (int i = N/2; i >= 0; i--) maxheap(arr, i); } public static void maxheap(int arr[], int i){ int left = 2*i ; int right = 2*i + 1; int max = i; if (left <= N && arr[left] > arr[i]) max = left; if (right <= N && arr[right] > arr[max]) max = right; if (max != i){ swap(arr, i, max); maxheap(arr, max); } } public static void swap(int arr[], int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args){ int n, i; System.out.println("Enter number of integer elements"); n = 10; int arr[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1}; System.out.println("\nElements before sorting "); for (i = 0; i < n; i++) System.out.print(arr[i]+" "); System.out.println(); sort(arr); System.out.println("\nElements after sorting "); for (i = 0; i < n; i++) System.out.print(arr[i]+" "); System.out.println(); } }

Output:

Output of Heap Sort Pseudocode Implementation in Java

Heap Sort Algorithm Time Complexity:

  • Build_max_heap takes O(logn) time
  • Swapping elements in the array takes O(1) time, but running it for n elements makes it O(n)
  • We're building max_heap for every element, so its time complexity becomes O(nlogn)
                 

Updated on 24 FEBRUARY, 2021 by Shaddy




Comments



You Might Also Like


Search
Get Answers to your Programming Questions


Recommended Deals ends in





Quiz For You:

Most Viewed Posts
Search Tags

    Heap Sort Pseudocode in Java

    Pseudocode for Heap Sort

    Algorithm for Heap Sort in Java

    Java Code for Heap Sort