Performance for this function should be O(n)

Question

Performance for this function should be O(n)

antonio081014 opened this issue 5 years ago · 3 comments

https://github.com/raywenderlich/swift-algorithm-club/blob/81bc0705cac3c1154a5bf248954034d7d532f2cb/Heap/Heap.swift#L215

In this function, index(of:) costs O(n), then remove(at:) costs O(log n), it should be O(n + log n), which would be O(n)

Answer 1 · 2019-10-09T17:11:40.000Z

https://github.com/raywenderlich/swift-algorithm-club/blob/81bc0705cac3c1154a5bf248954034d7d532f2cb/Heap/Heap.swift#L215:L221

Answer 2 · 2019-10-09T17:12:23.000Z

  /** Removes the first occurrence of a node from the heap. Performance: O(n log n). */
  @discardableResult public mutating func remove(node: T) -> T? {
    if let index = index(of: node) {
      return remove(at: index)
    }
    return nil
  }

Answer 3 · 2020-01-13T02:57:36.000Z

Fixed #905. Thanks!