In this tutorial, we’ll be discussing and implementing Heap data structures in Swift.

## Swift Heap

Heap can be either a max heap or a min heap.

In a max heap, the root node is the largest element and all the child nodes must be smaller than the parent. Min-heap works just the opposite way.

A heap is a specialized tree-based data structure.

The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.

If P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.

Nodes at the top are highest priority ones.

An illustration of a min heap is:

Table of Contents

### Heapify

Removing an element requires a rearrange of the heap data structure. This is termed as heapifying.

For example, if you delete the root node of the heap. For that, we need to swap it with the lowest node with the root node and then check the heap property recursively throughout.

heapifyUp() starts from the bottom and checks the heap properties all the way up.

heapifyDown() does just the opposite

Children of a node at N would be positioned at `2n+1`

and `2n+2`

in a max heap.

Let’s launch our XCode playground and create our heap using Swift.

We’ll build a heap structure using an array.

### Building a Heap

```
struct Heap<T> {
var elements = [T]()
var isEmpty: Bool { return elements.isEmpty }
var count: Int { return elements.count }
var isOrdered: (T, T) -> Bool
public init(sort: @escaping (T, T) -> Bool) {
self.isOrdered = sort
}
}
```

An escaping closure is passed which is used to save the function values. It compares the two values passed.

Add the following functions in the struct to get the indexes of the parent, left and right nodes:

```
func parentOf(_ index: Int) -> Int {
return (index - 1) / 2
}
func leftOf(_ index: Int) -> Int {
return (2 * index) + 1
}
func rightOf(_ index: Int) -> Int {
return (2 * index) + 2
}
```

heapifyDown():

```
mutating func heapifyDown(index: Int, heapSize: Int) {
var parentIndex = index
while true {
let leftIndex = self.leftOf(parentIndex)
let rightIndex = leftIndex + 1
var first = parentIndex
if leftIndex < heapSize && isOrdered(elements[leftIndex], elements[first]) {
first = leftIndex
}
if rightIndex < heapSize && isOrdered(elements[rightIndex], elements[first]) {
first = rightIndex
}
if first == parentIndex { return }
elements.swapAt(parentIndex, first)
parentIndex = first
}
}
mutating func shiftDown() {
heapifyDown(index: 0, heapSize: elements.count)
}
```

heapifyDown() is used while removing elements. heapifyUp() is used while inserting.

The following function is used to build the heap from the array:

```
mutating func buildHeap(fromArray array: [T]) {
elements = array
for i in stride(from: (elements.count/2 - 1), through: 0, by: -1) {
heapifyDown(index: i, heapSize: elements.count)
}
}
```

heapifyUp():

```
mutating func heapifyUp(index: Int) {
var nodeIndex = index
while true {
let parentIndex = self.parentOf(nodeIndex)
var first = parentIndex
if parentIndex >= 0 && isOrdered(elements[nodeIndex], elements[first]) {
first = nodeIndex
}
if first == parentIndex { return }
elements.swapAt(parentIndex, first)
nodeIndex = first
}
}
```

The following functions are used to insert and remove the elements from the heap:

Insert:

```
mutating func insert(value: T) {
self.elements.append(value)
heapifyUp(index: self.elements.count - 1)
}
```

Remove:

```
public mutating func remove(at index: Int) -> T? {
let temp: T
if index < 0 && count - 1 <= index {
return nil
}
temp = elements[index]
elements[index] = elements[count - 1]
elements.removeLast()
shiftDown()
return temp
}
```

Let’s use a sample input to test the above structure we’ve created:

```
let array: [Int] = [12,3,6,15,45,1,2]
var heap = Heap<Int>(sort: >)
heap.buildHeap(fromArray: array)
heap.insert(value: 23)
print(heap.elements)
print(heap.remove(at: 0))
print(heap.elements)
```

This brings an end to this tutorial on Swift Heap.

Thanks for the post – helps to have some practical code when reviewing a topic.

Just couple of things. Would be handy to know version of swift used. I tried the code in

$ swift -v

Apple Swift version 4.2.1 (swiftlang-1000.11.42 clang-1000.11.45.1)

and needed to fix a couple of things.

1)

struct Heap {

var elements = [T]()

becomes

struct Heap {

var elements: [T] = []

2)

and the } at the end of the first frame needs to move to the bottom of the last frame to encompass all the code into the strict definition

3)

The heap.swift:116:7: warning: expression implicitly coerced from ‘Int?’ to ‘Any’

print(heap.remove(at: 0))

can be fixed by

print(heap.remove(at: 0)!)

Cheers

Gannett