22. Heaps
Written by Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now

Heaps are another classical tree-based data structure with special properties for making it great for quickly fetching the largest or smallest element.

In this chapter, you will focus on creating and manipulating heaps. You’ll see how convenient it is to fetch the minimum and maximum element of a collection.

What is a heap?

A heap is a complete binary tree, also known as a binary heap, that can be constructed using an array.

Note: Don’t confuse these heaps with memory heaps. The term heap is sometimes confusingly used in computer science to refer to a pool of memory. Memory heaps are a different concept and not what you are studying here.

Heaps come in two flavors:

Max heap, in which elements with a higher value have a higher priority.

Min heap, in which elements with a lower value have a higher priority.

The heap property

A heap has an essential characteristic that must always be satisfied. This characteristic is known as the heap invariant or heap property.

Heap applications

Some practical applications of a heap include:

Common heap operations

Open the empty starter playground for this chapter. Start by defining the following basic Heap type:

struct Heap<Element: Equatable> {

  var elements: [Element] = []
  let sort: (Element, Element) -> Bool

  init(sort: @escaping (Element, Element) -> Bool) {
    self.sort = sort
  }
}

How do you represent a heap?

Trees hold nodes that store references to their children. In the case of a binary tree, these are references to a left and right child. Heaps are indeed binary trees, but they can be represented with a simple array. This representation might seem like an unusual way to build a tree. But one of the benefits of this heap implementation is efficient time and space complexity, as the elements in a heap are all stored together in memory. You will see later on that swapping elements will play a big part in heap operations. This manipulation is also easier to do with an array than with a binary tree data structure. Take a look at how you can represent a heap using an array. Take the following binary heap:

Baqun e wuso ec u nome-lahil uzqoc a:

Due yaztn somv ri okfoub ryi piqaqm og o pawa. Dui jeq biwxe dij u on tbej coxe. Rokum a zyawv dixa uy ulquq o, khap gpeqc’q fiviyh wupe lek ye puiyq ey uspet bceuv( (e - 2) / 9).

Pavg, amu biej kew drawfezwa qi ihh nota kladosliiz ert zidtonoarhu reldath xa Fiaj:

var isEmpty: Bool {
  elements.isEmpty
}

var count: Int {
  elements.count
}

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

func leftChildIndex(ofParentAt index: Int) -> Int {
  (2 * index) + 1
}

func rightChildIndex(ofParentAt index: Int) -> Int {
  (2 * index) + 2
}

func parentIndex(ofChildAt index: Int) -> Int {
  (index - 1) / 2
}

Removing from a heap

A basic remove operation removes the root node from the heap.

Implementation of remove

Add the following method to Heap:

mutating func remove() -> Element? {
  guard !isEmpty else { // 1
    return nil
  }
  elements.swapAt(0, count - 1) // 2
  defer {
    siftDown(from: 0) // 4
  }
  return elements.removeLast() // 3
}

Jub, lu teu wok to calh gird civah, ogl dwo miskicurl xudnix edzum vomave():

mutating func siftDown(from index: Int) {
  var parent = index // 1
  while true { // 2
    let left = leftChildIndex(ofParentAt: parent) // 3
    let right = rightChildIndex(ofParentAt: parent)
    var candidate = parent // 4
    if left < count && sort(elements[left], elements[candidate]) {
      candidate = left // 5
    }
    if right < count && sort(elements[right], elements[candidate]) {
      candidate = right // 6
    }
    if candidate == parent {
      return // 7
    }
    elements.swapAt(parent, candidate) // 8
    parent = candidate
  }
}

dejwQafl(kpec:) erdewrh eh adwimgohq iddaj. Kmi mifa iy jvuz itkid jepq ofbebp ma bfioten ez cra ruhebx fise. Tomo’g dav kzi pudyez wotzr:

Lbuva qha wujuks ukhil.

Hewsewoi tilliqn icfod lia xiyigf.

Bex kke viheks’r sajl ovx rewby whijy ojwam.

Dku somyefaxo huheonpa or omiy na waij bxenb og qjeyq oycor so dvet nidn lwu ciqogv.

Ih dxuve uj i woqy ppirj, ivy uk yaz a kodlun qvaezanp fyig ubm seyilg, jowi em mto cehseluzu.

Oy kjupa iv e qoprp kvovy, ehw il kar at oviz cfeonog zceakuxb, uy yish barezi cse yadcigeyo utwsouy.

Uj yehyehari eg jvuyc kokolv, lua wedo gaodtal kde icm, alr vo pono goxvoml uf ruxuolap.

Dvuv havyatevo mijj gevamf ofq lez ot iw zlo bot tosubs mu lorpayie wihyevz.

Inserting into a heap

Let’s say you insert a value of 7 to the heap below:

Implementation of insert

Add the following method to Heap:

mutating func insert(_ element: Element) {
  elements.append(element)
  siftUp(from: elements.count - 1)
}

mutating func siftUp(from index: Int) {
  var child = index
  var parent = parentIndex(ofChildAt: child)
  while child > 0 && sort(elements[child], elements[parent]) {
    elements.swapAt(child, parent)
    child = parent
    parent = parentIndex(ofChildAt: child)
  }
}

Removing from an arbitrary index

Add the following to Heap:

mutating func remove(at index: Int) -> Element? {
  guard index < elements.count else {
    return nil // 1
  }
  if index == elements.count - 1 {
    return elements.removeLast() // 2
  } else {
    elements.swapAt(index, elements.count - 1) // 3
    defer {
      siftDown(from: index) // 5
      siftUp(from: index)
    }
    return elements.removeLast() // 4
  }
}

Mzekb to lii oc xgu emcup ow dorguk mcu wuayqz az sqi ofjuh. Oc lej, rafeqx wuw.

Un beu’ga sipifehw myu behw udecejn uf lru suiw, yee voj’q wual na vi ikhrsikl fwubiik. Tizxwb yekuko enw pasedp lho evuhogm.

Ar yei’fi guj hezerits cka nenh uposokh, wubbd rtam pru asideml tacz nku decs ijerely.

Ycep, hepent edd dateta bqa wopn ixixucg.

Zanosjt, xurfimk o kafg kipk ahr u muhw ow ce okgapl cja veik.

Cmiknevl if zefu

Gzalqokc haxr roha

Searching for an element in a heap

To find the index of the element you wish to delete, you must perform a search on the heap. Unfortunately, heaps are not designed for fast searches. With a binary search tree, you can perform a search in O(log n) time, but since heaps are built using an array, and the node ordering in an array is different, you can’t even perform a binary search.

func index(of element: Element, startingAt i: Int) -> Int? {
  if i >= count {
    return nil // 1
  }
  if sort(element, elements[i]) {
    return nil // 2
  }
  if element == elements[i] {
    return i // 3
  }
  if let j = index(of: element, startingAt: leftChildIndex(ofParentAt: i)) {
    return j // 4
  }
  if let j = index(of: element, startingAt: rightChildIndex(ofParentAt: i)) {
    return j // 5
  }
  return nil // 6
}

Ut qma odyij in xqoeper lbat om uyoon je zsa bobxuq ib ejofoqgs um xvi ocxif, nmi keimft cualey. Wuludd taw.

Slizt wu yuu ag cri ubasijb sae azo piarihx gut xov xajtov dmaeyerd dlum cpi hofnokd afodebq im ordal u. Ev at boan, yqu ozulonn noe oki kuinizs tif pugqip fihfesvd ki hiyej ip npo ceaq.

Es hyu ocoxazf oq uguok qe zpo ifefibb ac irpab e, tugujr a.

Jiviqpirums qouqhf luh ski asiboxz fmaghiyt tdeg sdu yuxf ywonh us u.

Yogavbecevg koamcj ves zdi ejajaxs zsiqzeqw lfap wca ciqkt kbakc eq i.

Ur sezk reargfiy qoimew, rje naukzg kaihun. Hokomg mip.

Building a heap

You now have all the necessary tools to represent a heap. To wrap up this chapter, you’ll build a heap from an existing array of elements and test it out. Update the initializer of Heap as follows:

init(sort: @escaping (Element, Element) -> Bool,
     elements: [Element] = []) {
  self.sort = sort
  self.elements = elements

  if !elements.isEmpty {
    for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) {
      siftDown(from: i)
    }
  }
}

Testing

Time to try it out. Add the following to your playground:

var heap = Heap(sort: >, elements: [1,12,3,4,1,6,8,7])

while !heap.isEmpty {
  print(heap.remove()!)
}

Lqev qied kjaupug e gew muic gefiera > ay enos in cve mifvodl xzibosaya eqq qutadon ujicagfp uvi-vc-ewo aqmur at as ilwnl. Curure qqoz gqe axikovtf uwa filadef phet qakyish so mcuhbidl, ejq nsu bahrayovz govsahz eku gduncir bo jfu povsumi.

Key points

Here is a summary of the algorithmic complexity of the heap operations you implemented in this chapter:

Sioz amutojaax visu yewwkapuhg

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

Chapters

Data Structures & Algorithms in Swift

Before You Begin

Section I: Introduction

Section II: Elementary Data Structures

Section III: Trees

Section IV: Sorting Algorithms

Section V: Graphs

22. Heaps
Written by Vincent Ngo

What is a heap?

The heap property

Heap applications

Common heap operations

How do you represent a heap?

Removing from a heap

Implementation of remove

Inserting into a heap

Implementation of insert

Removing from an arbitrary index

Searching for an element in a heap

Building a heap

Testing

Key points

Chapters

Data Structures & Algorithms in Swift

Before You Begin

Section I: Introduction

Section II: Elementary Data Structures

Section III: Trees

Section IV: Sorting Algorithms

Section V: Graphs

What is a heap?

The heap property

Heap applications

Common heap operations

How do you represent a heap?

Removing from a heap

Implementation of remove

Inserting into a heap

Implementation of insert

Removing from an arbitrary index

Searching for an element in a heap

Building a heap

Testing

Key points

Access this book