• API
• FAQ
• Tools
• Archive
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.

Top