Skip to content

Instantly share code, notes, and snippets.

@emmasteimann
Created September 10, 2016 16:16
Show Gist options
  • Save emmasteimann/838a3e33693678f53e85f8caf46a6fb7 to your computer and use it in GitHub Desktop.
Save emmasteimann/838a3e33693678f53e85f8caf46a6fb7 to your computer and use it in GitHub Desktop.
Swift MinHeap
class MinHeap {
var harr:[Int] = Array<Int>()
init() {
}
func getMin() -> Int {
return harr[0]
}
func left(num:Int) -> Int {
return num * 2 + 1;
}
func right(num:Int) -> Int {
return num * 2 + 2;
}
func parent(num:Int) -> Int {
return num == 0 ? -1 : (num-1)/2
}
func insert(num:Int) {
harr.append(num)
if (harr.count > 1){
let index = harr.count - 1
bubbleUp(index)
}
print(harr)
}
func removeMin() -> Int {
print("Before removing Min: \(harr)")
let currentMin = harr[0]
let lastItem = harr.removeAtIndex(harr.count - 1)
harr[0] = lastItem
bubbleDown(0)
print("After removing Min: \(harr)")
return currentMin
}
func bubbleUp(index:Int) {
var idx = index
var parentItemIndex = parent(idx)
while idx > 0 && harr[parentItemIndex] > harr[idx] {
print("\(index) vs \(parentItemIndex)")
let currentItem = harr[idx]
let parentItem = harr[parentItemIndex]
harr[idx] = parentItem
harr[parentItemIndex] = currentItem
print(parentItemIndex)
idx = parentItemIndex
parentItemIndex = parent(idx)
}
}
func bubbleDown(index:Int) {
var idx = index
var minChildIdx = minChildIndex(idx)
if minChildIdx != -1 && harr[minChildIdx] < harr[idx] {
let currentItem = harr[idx]
let childItem = harr[minChildIdx]
harr[idx] = childItem
harr[minChildIdx] = currentItem
idx = minChildIdx
minChildIdx = minChildIndex(idx)
}
}
func minChildIndex(num:Int) -> Int {
if left(num) > (harr.count - 1) { return -1 }
if right(num) > (harr.count - 1) { return left(num) }
return harr[left(num)] <= harr[right(num)] ? left(num) : right(num)
}
}
var minHeap = MinHeap()
minHeap.insert(50)
minHeap.insert(20)
minHeap.insert(10)
minHeap.insert(7)
print("Remove Min")
print(minHeap.getMin())
minHeap.removeMin()
print(minHeap.getMin())
minHeap.removeMin()
print(minHeap.getMin())
minHeap.removeMin()
print(minHeap.getMin())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment