# Swift Algorithm Club: Heap and Priority Queue Data Structure

In this Swift Algorithm Club tutorial, you’ll learn how to implement a heap in Swift 3, a way to implement a priority queue. By Ross O'Brien.

### Sign up/Sign in

With a **free** Kodeco account you can download source code, track your progress,
bookmark, personalise your learner profile and more!

Already a member of Kodeco? Sign in

### Sign up/Sign in

With a **free** Kodeco account you can download source code, track your progress,
bookmark, personalise your learner profile and more!

Already a member of Kodeco? Sign in

## Contents

## Swift Algorithm Club: Heap and Priority Queue Data Structure

25 mins

### Simple functions

All the code snippets in this section are small, independent computed properties or functions. Remove the `TODO`

comment for priority queue functions, and replace it with these.

```
var isEmpty : Bool {
return elements.isEmpty
}
var count : Int {
return elements.count
}
```

You might recognize these property names from using arrays, or from the `Queue`

data structure. The `Heap`

is empty if its `elements`

array is empty, and its count is the `elements`

array’s count. We’ll be needing to know how many elements are in the heap a lot in the coming code.

Below the two computed properties, add this function:

```
func peek() -> Element? {
return elements.first
}
```

This will definitely be familiar to you if you’ve used the `Queue`

. All it does is return the first element in the array – allowing the caller to access the element with the highest priority in the heap.

Now remove the `TODO`

comment for helper functions, and replace it with these four functions:

```
func isRoot(_ index: Int) -> Bool {
return (index == 0)
}
func leftChildIndex(of index: Int) -> Int {
return (2 * index) + 1
}
func rightChildIndex(of index: Int) -> Int {
return (2 * index) + 2
}
func parentIndex(of index: Int) -> Int {
return (index - 1) / 2
}
```

These four functions are all about taking the formula of calculating the array indices of child or parent nodes, and hiding them inside easy to read function calls.

You might have realised that the formula for calculating the child indices only tell you what the left or right child indices should be. They don’t use optionals or throw errors to suggest that the heap might be too small to actually have an element at those indices. We’ll have to be mindful of this.

You might also have realised that because of the left and right child index formula, or because of the tree diagrams above, all left children will have odd indices and all right children will have even indices. However, the `parentIndex`

function doesn’t attempt to determine if the `index`

argument is a left or right child before calculating the parent index; it just uses integer division to get the answer.

### Comparing priority

In the theory, we compared the priorities of elements with their parent or children nodes a lot. In this section we determine which index, of a node and its children, points to the highest priority element.

Below the `parentIndex`

function, add this function:

```
func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool {
return priorityFunction(elements[firstIndex], elements[secondIndex])
}
```

This helper function is a wrapper for the priority function property. It takes two indices and returns `true`

if the element at the first index has higher priority.

This helps us write two more comparison helper functions, which you can now write below `isHigherPriority`

:

```
func highestPriorityIndex(of parentIndex: Int, and childIndex: Int) -> Int {
guard childIndex < count && isHigherPriority(at: childIndex, than: parentIndex)
else { return parentIndex }
return childIndex
}
func highestPriorityIndex(for parent: Int) -> Int {
return highestPriorityIndex(of: highestPriorityIndex(of: parent, and: leftChildIndex(of: parent)), and: rightChildIndex(of: parent))
}
```

Let’s review these two functions. The first assumes that a parent node has a valid index in the array, checks if the child node has a valid index in the array, and then compares the priorities of the nodes at those indices, and returns a valid index for whichever node has the highest priority.

The second function also assumes that the parent node index is valid, and compares the index to both of its left and right children – if they exist. Whichever of the three has the highest priority is the index returned.

The last helper function is another wrapper, and it’s the only helper function which changes the `Heap`

data structure at all.

```
mutating func swapElement(at firstIndex: Int, with secondIndex: Int) {
guard firstIndex != secondIndex
else { return }
swap(&elements[firstIndex], &elements[secondIndex])
}
```

This function takes two indices, and swaps the elements at those indices. Because Swift throws a runtime error if the caller attempts to swap array elements with the same index, we `guard`

for this and return early if the indices are the same.

### Enqueueing a new element

If we’ve written useful helper functions, then the big and important functions should now be easy to write. So, first we’re going to write a function which enqueues a new element to the last position in the heap, and then sift it up.

It looks as simple as you would expect. Write this with the priority queue functions, under the `peek()`

function:

```
mutating func enqueue(_ element: Element) {
elements.append(element)
siftUp(elementAtIndex: count - 1)
}
```

`count - 1`

is the highest legal index value in the array, with the new element added.

This won’t compile until you write the `siftUp`

function, though:

```
mutating func siftUp(elementAtIndex index: Int) {
let parent = parentIndex(of: index) // 1
guard !isRoot(index), // 2
isHigherPriority(at: index, than: parent) // 3
else { return }
swapElement(at: index, with: parent) // 4
siftUp(elementAtIndex: parent) // 5
}
```

Now we see all the helper functions coming to good use! Let’s review what you’ve written.

- First you calculate what the parent index of the index argument is, because it’s used several times in this function and you only need to calculate it once.
- Then you
`guard`

to ensure you’re not trying to sift up the root node of the heap, - or sift an element up above a higher priority parent. The function ends if you attempt either of these things.
- Once you know the indexed node has a higher priority than its parent, you swap the two values,
- and call
`siftUp`

on the parent index, in case the element isn’t yet in position.

This is a recursive function. It keeps calling itself until its terminal conditions are reached.

### Dequeueing the highest priority element

What we can sift up, we can sift down, surely.

To dequeue the highest priority element, and leave a consistent heap behind, write the following function under the `siftUp`

function:

```
mutating func dequeue() -> Element? {
guard !isEmpty // 1
else { return nil }
swapElement(at: 0, with: count - 1) // 2
let element = elements.removeLast() // 3
if !isEmpty { // 4
siftDown(elementAtIndex: 0) // 5
}
return element // 6
}
```

Let’s review what you’ve written.

- First you
`guard`

that that the heap has a first element to return. If there isn’t, you return`nil`

. - If there is an element, you swap it with the last node in the heap.
- Now you remove the highest priority element from the last position in the heap, and store it in
`element`

. - If the heap isn’t empty now, then you sift the current root element down the heap to its proper prioritized place.
- Finally you return the highest priority element from the function.

This won’t compile without the accompanying `siftDown`

function:

```
mutating func siftDown(elementAtIndex index: Int) {
let childIndex = highestPriorityIndex(for: index) // 1
if index == childIndex { // 2
return
}
swapElement(at: index, with: childIndex) // 3
siftDown(elementAtIndex: childIndex)
}
```

Let’s review this function too:

- First you find out which index, of the argument index and its child indices, points to the element with the highest priority. Remember that if the argument index is a leaf node in the heap, it has no children, and the
`highestPriorityIndex(for:)`

function will return the argument index. - If the argument index is that index, then you stop sifting here.
- If not, then one of the child elements has a higher priority; swap the two elements, and keep recursively sifting down.