title: How to implement PriorityQueue using min-heap in Swift?
body: <p>First of all, is there a built-in "PriorityQueue"-like class in Swift standard library? I am unable to find one, therefore I'm writing it myself.</p>
  
  <p>When I pop items from my queue, I expect the item to be the smallest at the moment. For most items, this is true, but some of them (very few) are not in the right positions and I can't seem to find out why. The below code snippet can be copy-pasted in Playground and run (including tests).</p>
  
  <pre class="lang-swift prettyprint-override"><code>class PriorityQueue&lt;T&gt; {
      private var arr: [T] = []
      private let compare: (_ a: T, _ b: T) -&gt; Bool
  
      init(_ compare: @escaping (_ a: T, _ b: T) -&gt; Bool) {
          self.compare = compare
      }
  
      func insert(_ a: T) {
          arr.insert(a, at: 0)
          heapify(0)
      }
  
      func pop() -&gt; T? {
          if arr.isEmpty {
              return nil
          }
  
          let res: T = arr.removeFirst()
  
          if !arr.isEmpty {
              arr.insert(arr.removeLast(), at: 0)
              heapify(0)
          }
  
          return res
      }
  
      private func heapify(_ i: Int) {
          let l: Int = 2 * i + 1, r: Int = 2 * i + 2
          var smallest: Int = i
  
          if l &lt; arr.count, compare(arr[l], arr[smallest]) {
              smallest = l
          }
  
          if r &lt; arr.count, compare(arr[r], arr[smallest]) {
              smallest = r
          }
  
          if smallest == i {
              return
          }
  
          let temp: T = arr[i]
          arr[i] = arr[smallest]
          arr[smallest] = temp
  
          heapify(smallest)
      }
  }
  
  // Test case
  let size: Int = 15
  var arr: [Int] = Array(repeating: 0, count: size)
  let queue: PriorityQueue&lt;Int&gt; = PriorityQueue { $0 &lt; $1 }
  
  for i in 0..&lt;size {
      arr[i] = Int.random(in: 1...10000)
      queue.insert(arr[i])
  }
  
  let sorted: [Int] = arr.sorted()
  for i in 0..&lt;size {
      let n: Int = queue.pop() ?? 0
      print(n, sorted[i], n == sorted[i])
  }
  </code></pre>
  
  <p>95% of the times, items are being popped from the queue in correct order, but occasionally, I get results like this:</p>
  
  <p>579  579 true</p>
  
  <p>1372 1372 true</p>
  
  <p>1762 1762 true</p>
  
  <p>2113 2113 true</p>
  
  <p>2332 2332 true</p>
  
  <p><strong>2562 2418 false</strong></p>
  
  <p><strong>2701 2562 false</strong></p>
  
  <p><strong>3137 2701 false</strong></p>
  
  <p><strong>2418 3137 false</strong></p>
  
  <p>4615 4615 true</p>
  
  <p>6085 6085 true</p>
  
  <p>6820 6820 true</p>
  
  <p>7382 7382 true</p>
  
  <p>8878 8878 true</p>
  
  <p>9220 9220 true</p>