Heap Sort Algorithm or Pseudocode Implemented in Java

(257 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)

Solution Worked 0 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote



Comments



Search