Skip to content

Instantly share code, notes, and snippets.

@derekli66
Created July 20, 2019 03:27
Show Gist options
  • Save derekli66/f4bd93ff0a7079d8dd2d7c7405395673 to your computer and use it in GitHub Desktop.
Save derekli66/f4bd93ff0a7079d8dd2d7c7405395673 to your computer and use it in GitHub Desktop.
import UIKit
var arr = [Int?]()
arr.append(nil)
func parent(_ i: Int) -> Int {
return i/2
}
func left(_ i: Int) -> Int {
return 2 * i
}
func right(_ i: Int) -> Int {
return 2 * i + 1
}
func insert(_ val: Int) {
arr.append(val)
var childIndex = arr.count - 1
var parentIndex = parent(childIndex)
while (parentIndex > 0) {
if arr[parentIndex]! < arr[childIndex]! {
arr.swapAt(parentIndex, childIndex)
}
childIndex = parentIndex
parentIndex = parent(childIndex)
}
}
func maxHeapify(_ idx: Int) {
if idx == 0 { return }
var largestIdx = idx
let leftIdx = left(idx)
let rightIdx = right(idx)
if leftIdx < arr.count && arr[leftIdx]! > arr[largestIdx]! {
largestIdx = leftIdx
}
if rightIdx < arr.count && arr[rightIdx]! > arr[largestIdx]! {
largestIdx = rightIdx
}
if largestIdx != idx {
arr.swapAt(largestIdx, idx)
maxHeapify(largestIdx)
}
}
func pop() -> Int? {
if arr.count <= 1 { return nil }
let first = 1
let end = arr.count - 1
arr.swapAt(first, end)
let result = arr[end]
arr.remove(at: end)
maxHeapify(first)
return result
}
var unsorted = [3, 2, 3, 1, 2, 4, 5, 5, 6]
for i in 0..<unsorted.count {
insert(unsorted[i])
}
while (true) {
let element = pop()
if element == nil { break }
print("\(element)")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment