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