1 class Solution {
  2     func connectSticks(_ sticks: [Int]) -> Int {
  3         var pq:PriorityQueue<Int> = PriorityQueue<Int> { $0 < $1 }
  4         for v in sticks
  5         {
  6             pq.push(v)
  7         }
  8         var ans:Int = 0
  9         while(pq.count > 1)
 10         {
 11             let x:Int = pq.pop()!
 12             let y:Int = pq.pop()!
 13             let sum:Int = x + y
 14             ans += sum
 15             pq.push(sum)            
 16         }
 17         return ans
 18     }
 19 }
 20 
 21 public struct PriorityQueue<T> {
 22   fileprivate var heap: Heap<T>
 23   public init(sort: @escaping (T, T) -> Bool) {
 24     heap = Heap(sort: sort)
 25   }
 26 
 27   public var isEmpty: Bool {
 28     return heap.isEmpty
 29   }
 30 
 31   public var count: Int {
 32     return heap.count
 33   }
 34 
 35   public func peek() -> T? {
 36     return heap.peek()
 37   }
 38 
 39   public mutating func push(_ element: T) {
 40     heap.insert(element)
 41   }
 42 
 43   public mutating func pop() -> T? {
 44     return heap.remove()
 45   }
 46 
 47   public mutating func changePriority(index i: Int, value: T) {
 48     return heap.replace(index: i, value: value)
 49   }
 50 }
 51 
 52 extension PriorityQueue where T: Equatable {
 53   public func index(of element: T) -> Int? {
 54     return heap.index(of: element)
 55   }
 56 }
 57 
 58 public struct Heap<T> {
 59   var nodes = [T]()
 60 
 61   private var orderCriteria: (T, T) -> Bool
 62 
 63   public init(sort: @escaping (T, T) -> Bool) {
 64     self.orderCriteria = sort
 65   }
 66   
 67   public init(array: [T], sort: @escaping (T, T) -> Bool) {
 68     self.orderCriteria = sort
 69     configureHeap(from: array)
 70   }
 71 
 72   private mutating func configureHeap(from array: [T]) {
 73     nodes = array
 74     for i in stride(from: (nodes.count/2-1), through: 0, by: -1) {
 75       shiftDown(i)
 76     }
 77   }
 78   
 79   public var isEmpty: Bool {
 80     return nodes.isEmpty
 81   }
 82   
 83   public var count: Int {
 84     return nodes.count
 85   }
 86 
 87   @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {
 88     return (i - 1) / 2
 89   }
 90 
 91   @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int {
 92     return 2*i + 1
 93   }
 94 
 95   @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int {
 96     return 2*i + 2
 97   }
 98   
 99   public func peek() -> T? {
100     return nodes.first
101   }
102   
103   public mutating func insert(_ value: T) {
104     nodes.append(value)
105     shiftUp(nodes.count - 1)
106   }
107   
108   public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
109     for value in sequence {
110       insert(value)
111     }
112   }
113   
114   public mutating func replace(index i: Int, value: T) {
115     guard i < nodes.count else { return }
116     
117     remove(at: i)
118     insert(value)
119   }
120 
121   @discardableResult public mutating func remove() -> T? {
122     guard !nodes.isEmpty else { return nil }
123     
124     if nodes.count == 1 {
125       return nodes.removeLast()
126     } else {
127       let value = nodes[0]
128       nodes[0] = nodes.removeLast()
129       shiftDown(0)
130       return value
131     }
132   }
133   
134   @discardableResult public mutating func remove(at index: Int) -> T? {
135     guard index < nodes.count else { return nil }
136     
137     let size = nodes.count - 1
138     if index != size {
139       nodes.swapAt(index, size)
140       shiftDown(from: index, until: size)
141       shiftUp(index)
142     }
143     return nodes.removeLast()
144   }
145 
146   internal mutating func shiftUp(_ index: Int) {
147     var childIndex = index
148     let child = nodes[childIndex]
149     var parentIndex = self.parentIndex(ofIndex: childIndex)
150     
151     while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
152       nodes[childIndex] = nodes[parentIndex]
153       childIndex = parentIndex
154       parentIndex = self.parentIndex(ofIndex: childIndex)
155     }
156     
157     nodes[childIndex] = child
158   }
159 
160   internal mutating func shiftDown(from index: Int, until endIndex: Int) {
161     let leftChildIndex = self.leftChildIndex(ofIndex: index)
162     let rightChildIndex = leftChildIndex + 1
163 
164     var first = index
165     if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
166       first = leftChildIndex
167     }
168     if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
169       first = rightChildIndex
170     }
171     if first == index { return }
172     
173     nodes.swapAt(index, first)
174     shiftDown(from: first, until: endIndex)
175   }
176   
177   internal mutating func shiftDown(_ index: Int) {
178     shiftDown(from: index, until: nodes.count)
179   }
180   
181 }
182 
183 extension Heap where T: Equatable {
184     
185     public func index(of node: T) -> Int? {
186         return nodes.firstIndex(where: { $0 == node })
187     }
188     
189     @discardableResult public mutating func remove(node: T) -> T? {
190         if let index = index(of: node) {
191             return remove(at: index)
192         }
193         return nil
194     }
195 }