Group Group Group Group Group Group Group Group Group

Need help understanding sort() function in Heap

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

    mutating func siftDown(from index: Int) {
            var parent = index
    
            while true {
                    let left = leftChildIndex(ofParentAt: parent)
                    let right = rightChildIndex(ofParentAt: parent)
        
                    var candidate = parent

                    if left < count && sort(elements[left], elements[candidate]) {
                            candidate = left
                    }
                    if right < count && sort(elements[right], elements[candidate]) {
                            candidate = right
                    }
                    if candidate == parent {
                            return
                    }
        
                    elements.swapAt(parent, candidate)
                    parent = candidate
            }
    }

Can someone explain how the sort function is working here / what it’s doing?

#2

@anothershitdev Please let me know which chapter is the function from when you get a chance. Thank you!

#3

This is from chapter 21 - heaps @shogunkaramazov

#4

@kelvin_lau Can you please help with this when you get a chance? Thank you - much appreciated! :]

#5

Pinging @jomoka!

Can you please help with this when you get a chance?

#6

@anothershitdev

Hi sorry for the late reply.

But if you have a look at the heap’s initializer. The sort function is required whenever you initialize a heap. It probably could have been named priority for clarity. But the goal is to provide a custom function to determine how to sort or prioritize the elements. For example in a max heap, the left and right child has to be less than the parent. The sort function is just to compare two elements, and determine which elements we need to swap. Hope this makes sense!

struct Heap<Element: Equatable> {
  
  var elements: [Element] = []
  let sort: (Element, Element) -> Bool
  
  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)
      }
    }
  }