daily pastebin goal
15%
SHARE
TWEET

Untitled

a guest Feb 16th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. object HeapSort:SortInterface {
  2.     override fun <T : Comparable<T>> sort(arr: Array<T>) {
  3.         for (i in arr.size / 2 downTo 0) {
  4.             maxHeapify(arr, i)
  5.         }
  6.         for (i in arr.size - 1 downTo 1) {
  7.             val tempMax = arr[0]
  8.             arr[0] = arr[i]
  9.             arr[i] = tempMax
  10.             maxHeapifyWithRange(arr,0,i-1)
  11.         }
  12.     }
  13.  
  14.     private fun <T : Comparable<T>> maxHeapify(arr: Array<T>, i: Int) {
  15.         var largest = if (i.left() < arr.size && arr[i.left()] > arr[i]) {
  16.             i.left()
  17.         } else {
  18.             i
  19.         }
  20.         if (i.right() < arr.size && arr[i.right()] > arr[largest]) {
  21.             largest = i.right()
  22.         }
  23.         if (largest != i) {
  24.             val temp = arr[i]
  25.             arr[i] = arr[largest]
  26.             arr[largest] = temp
  27.             maxHeapify(arr, largest)
  28.         }
  29.     }
  30.  
  31.     private fun <T : Comparable<T>> maxHeapifyWithRange(arr: Array<T>, i: Int, limit: Int) {
  32.         var largest = if (i.left() <= limit && arr[i.left()] > arr[i]) {
  33.             i.left()
  34.         } else {
  35.             i
  36.         }
  37.         if (i.right() <= limit && arr[i.right()] > arr[largest]) {
  38.             largest = i.right()
  39.         }
  40.         if (largest != i) {
  41.             val temp = arr[i]
  42.             arr[i] = arr[largest]
  43.             arr[largest] = temp
  44.             maxHeapifyWithRange(arr, largest, limit)
  45.         }
  46.     }
  47.    
  48.     val left = fun Int.(): Int = 2 * this
  49.     val right = fun Int.(): Int = 2 * this + 1
  50. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top