Chapter 22: The Heap Data Structure

📚 Official Books Data Structures & Algorithms in Swift
1

Searching for an element in a heap

func index(of element: Element, startingAt i: Int) -> Int? {

      if i >= count {
        return nil
      }

      if sort(element, elements[i]) {
        return nil
      }

      if element == elements[i] {
       return i 
      }

      if let j = index(of: element, startingAt: leftChildIndex(ofParentAt: i)) {
          return j
      }

      if let j = index(of: element, startingAt: rightChildIndex(ofParentAt: i)) {
          return j
      }

      return nil
}

For searching element in Heap, where we are not assure which child subtree can have the element, how can we depend upon the sort function(as we are using it as 2nd condition in our function)?

2

@shogunkaramazov can u plz help in this

3

@pulkitap Do you still have issues with this?

4

@shogunkaramazov Yes… I am still not clear with this.

5

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

6

@pulkitap sorry for the late reply!

This is a recursive function. sort function just compares two elements. Depending on whether it is a max or min heap.

If it’s a max heap, the sort function will compare whether the element > currentElement

If it’s a min heap, the sort function will compare whether the element < currentElement

In any case this is true, then the element does not exist in the heap.
Recall that in a max heap, the root element has the greatest value.
Recall that in a min heap, the root element has the smallest value.

This is why we have to recursively check the left and right child to find the element.