1 class Solution {
 2     func medianSlidingWindow(_ nums: [Int], _ k: Int) -> [Double] {
 3         var k = k
 4         var res:[Double] = [Double]()
 5         var record:[(Int,Int)] = [(Int,Int)]()
 6         for i in 0..<k
 7         {
 8             record.append((nums[i],i))
 9         }
10         record.sort(by: cmp)
11         update(&res, &record, &k)
12         for i in k..<nums.count
13         {
14             record.remove(at: beforePos(&record, i - k))
15             record.insert((nums[i],i), at: binPos(&record, nums[i]))
16             update(&res, &record, &k)
17         }
18         return res
19     }
20     
21     func cmp(_ a:(Int,Int),_ b:(Int,Int)) -> Bool
22     {
23         if a.0 == b.0 {return a.1 < b.1}
24         return a.0 < b.0
25     }
26     
27     func binPos(_ record:inout [(Int,Int)],_ target:Int) -> Int
28     {
29         var left:Int = 0
30         var right:Int = record.count
31         while(left < right)
32         {
33             let middle:Int = left + (right - left) / 2
34             if record[ middle].0 == target
35             {
36                 return middle
37             }
38             else if record[ middle].0 < target
39             {
40                 left = middle + 1
41             }
42             else
43             {
44                 right = middle
45             }
46         }
47         return left
48     }
49     
50     func beforePos(_ record:inout [(Int,Int)],_ j:Int) -> Int
51     {
52         for i in 0..<record.count
53         {
54             if record[i].1 == j
55             {
56                 return i
57             }
58         }
59         return 0
60     }
61     
62     func update(_ res:inout [Double],_ record:inout [(Int,Int)],_ k:inout Int )
63     {
64         if k % 2 == 1
65         {
66             res.append(Double(record[ record.count / 2].0))
67         }
68         else
69         {
70             res.append(Double(record[ record.count / 2].0) * 1.0 / 2 + Double(record[ record.count/2-1].0) * 1.0 / 2)
71         }
72     }
73 }

  1 class Solution {
  2     var maxHeap = Heap<Int>(sort: >)
  3 var minHeap = Heap<Int>(sort: <)
  4 
  5 func medianSlidingWindow(_ nums: [Int], _ k: Int) -> [Double] {
  6     var res = [Double]()
  7     
  8     for (index, value) in nums.enumerated() {
  9         if maxHeap.isEmpty || value <= maxHeap.peek()! {
 10             maxHeap.insert(value)
 11         } else {
 12             minHeap.insert(value)
 13         }
 14         
 15         balance()
 16         
 17         let removeTarget = index - k
 18         if removeTarget >= 0 {
 19             if nums[removeTarget] > maxHeap.peek()! {
 20                 minHeap.remove(node: nums[removeTarget])
 21             } else {
 22                 maxHeap.remove(node: nums[removeTarget])
 23             }
 24         }
 25         
 26         balance()
 27         
 28         if index >= k - 1 {
 29             if k % 2 == 0 {
 30                 res.append((Double(minHeap.peek()!) + Double(maxHeap.peek()!)) / 2)
 31             } else {
 32                 res.append(Double(maxHeap.peek()!))
 33             }
 34         }
 35     }
 36     
 37     return res
 38 }
 39 
 40 func balance() {
 41     while maxHeap.count < minHeap.count {
 42         maxHeap.insert(minHeap.remove()!)
 43     }
 44     
 45     while minHeap.count < maxHeap.count - 1 {
 46         minHeap.insert(maxHeap.remove()!)
 47     }
 48   }
 49 }
 50 
 51 
 52 ////// swfit heap:
 53 public struct Heap<T> {
 54     /** The array that stores the heap's nodes. */
 55     var nodes = [T]()
 56     
 57     /**
 58      * Determines how to compare two nodes in the heap.
 59      * Use '>' for a max-heap or '<' for a min-heap,
 60      * or provide a comparing method if the heap is made
 61      * of custom elements, for example tuples.
 62      */
 63     private var orderCriteria: (T, T) -> Bool
 64     
 65     /**
 66      * Creates an empty heap.
 67      * The sort function determines whether this is a min-heap or max-heap.
 68      * For comparable data types, > makes a max-heap, < makes a min-heap.
 69      */
 70     public init(sort: @escaping (T, T) -> Bool) {
 71         orderCriteria = sort
 72     }
 73     
 74     /**
 75      * Creates a heap from an array. The order of the array does not matter;
 76      * the elements are inserted into the heap in the order determined by the
 77      * sort function. For comparable data types, '>' makes a max-heap,
 78      * '<' makes a min-heap.
 79      */
 80     public init(array: [T], sort: @escaping (T, T) -> Bool) {
 81         orderCriteria = sort
 82         configureHeap(from: array)
 83     }
 84     
 85     /**
 86      * Configures the max-heap or min-heap from an array, in a bottom-up manner.
 87      * Performance: This runs pretty much in O(n).
 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     /**
105      * Returns the index of the parent of the element at index i.
106      * The element at index 0 is the root of the tree and has no parent.
107      */
108     @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {
109         return (i - 1) / 2
110     }
111     
112     /**
113      * Returns the index of the left child of the element at index i.
114      * Note that this index can be greater than the heap size, in which case
115      * there is no left child.
116      */
117     @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int {
118         return 2 * i + 1
119     }
120     
121     /**
122      * Returns the index of the right child of the element at index i.
123      * Note that this index can be greater than the heap size, in which case
124      * there is no right child.
125      */
126     @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int {
127         return 2 * i + 2
128     }
129     
130     /**
131      * Returns the maximum value in the heap (for a max-heap) or the minimum
132      * value (for a min-heap).
133      */
134     public func peek() -> T? {
135         return nodes.first
136     }
137     
138     /**
139      * Adds a new value to the heap. This reorders the heap so that the max-heap
140      * or min-heap property still holds. Performance: O(log n).
141      */
142     public mutating func insert(_ value: T) {
143         nodes.append(value)
144         shiftUp(nodes.count - 1)
145     }
146     
147     /**
148      * Adds a sequence of values to the heap. This reorders the heap so that
149      * the max-heap or min-heap property still holds. Performance: O(log n).
150      */
151     public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
152         for value in sequence {
153             insert(value)
154         }
155     }
156     
157     /**
158      * Allows you to change an element. This reorders the heap so that
159      * the max-heap or min-heap property still holds.
160      */
161     public mutating func replace(index i: Int, value: T) {
162         guard i < nodes.count else { return }
163         
164         remove(at: i)
165         insert(value)
166     }
167     
168     /**
169      * Removes the root node from the heap. For a max-heap, this is the maximum
170      * value; for a min-heap it is the minimum value. Performance: O(log n).
171      */
172     @discardableResult public mutating func remove() -> T? {
173         guard !nodes.isEmpty else { return nil }
174         
175         if nodes.count == 1 {
176             return nodes.removeLast()
177         } else {
178             // Use the last node to replace the first one, then fix the heap by
179             // shifting this new first node into its proper position.
180             let value = nodes[0]
181             nodes[0] = nodes.removeLast()
182             shiftDown(0)
183             return value
184         }
185     }
186     
187     /**
188      * Removes an arbitrary node from the heap. Performance: O(log n).
189      * Note that you need to know the node's index.
190      */
191     @discardableResult public mutating func remove(at index: Int) -> T? {
192         guard index < nodes.count else { return nil }
193         
194         let size = nodes.count - 1
195         if index != size {
196             nodes.swapAt(index, size)
197             shiftDown(from: index, until: size)
198             shiftUp(index)
199         }
200         return nodes.removeLast()
201     }
202     
203     /**
204      * Takes a child node and looks at its parents; if a parent is not larger
205      * (max-heap) or not smaller (min-heap) than the child, we exchange them.
206      */
207     internal mutating func shiftUp(_ index: Int) {
208         var childIndex = index
209         let child = nodes[childIndex]
210         var parentIndex = self.parentIndex(ofIndex: childIndex)
211         
212         while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
213             nodes[childIndex] = nodes[parentIndex]
214             childIndex = parentIndex
215             parentIndex = self.parentIndex(ofIndex: childIndex)
216         }
217         
218         nodes[childIndex] = child
219     }
220     
221     /**
222      * Looks at a parent node and makes sure it is still larger (max-heap) or
223      * smaller (min-heap) than its childeren.
224      */
225     internal mutating func shiftDown(from index: Int, until endIndex: Int) {
226         let leftChildIndex = self.leftChildIndex(ofIndex: index)
227         let rightChildIndex = leftChildIndex + 1
228         
229         // Figure out which comes first if we order them by the sort function:
230         // the parent, the left child, or the right child. If the parent comes
231         // first, we're done. If not, that element is out-of-place and we make
232         // it "float down" the tree until the heap property is restored.
233         var first = index
234         if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
235             first = leftChildIndex
236         }
237         if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
238             first = rightChildIndex
239         }
240         if first == index { return }
241         
242         nodes.swapAt(index, first)
243         shiftDown(from: first, until: endIndex)
244     }
245     
246     internal mutating func shiftDown(_ index: Int) {
247         shiftDown(from: index, until: nodes.count)
248     }
249 }
250 
251 // MARK: - Searching
252 
253 extension Heap where T: Equatable {
254     /** Get the index of a node in the heap. Performance: O(n). */
255     public func index(of node: T) -> Int? {
256         return nodes.index(where: { $0 == node })
257     }
258     
259     /** Removes the first occurrence of a node from the heap. Performance: O(n log n). */
260     @discardableResult public mutating func remove(node: T) -> T? {
261         if let index = index(of: node) {
262             return remove(at: index)
263         }
264         return nil
265     }
266 }