1
class MedianFinder {
2

3
    var minStack = SwiftPriorityQueue<Int>(hasHigherPriority: { $0 > $1 }, isEqual: { $0 == $1 })
4
    var maxStack = SwiftPriorityQueue<Int>(hasHigherPriority: { $0 < $1 }, isEqual: { $0 == $1 })
5

6
    /** initialize your data structure here. */
7
    init() {
8

9
    }
10

11
    func addNum(_ num: Int) {
12
        if maxStack.count > minStack.count {
13
            minStack.enqueue(num)
14
        }
15
        else if minStack.count > maxStack.count {
16
            maxStack.enqueue(num)
17
        }
18
        else {
19
            if let minMax = minStack.array().first, minMax > num {
20
                minStack.enqueue(num)
21
            }
22
            else if let maxMin = maxStack.array().first, maxMin < num {
23
                maxStack.enqueue(num)
24
            }
25
            else {
26
                maxStack.enqueue(num)
27
            }
28
        }
29

30
        if let minMax = minStack.array().first, let maxMin = maxStack.array().first, minMax > maxMin {
31
            minStack.dequeue()
32
            minStack.enqueue(maxMin)
33

34
            maxStack.dequeue()
35
            maxStack.enqueue(minMax)
36
        }
37

38
//        print("大堆：\(maxStack)")
39
//        print("小堆：\(minStack)")
40
//        print("======")
41
    }
42

43
    func findMedian() -> Double {
44
        if minStack.count == maxStack.count, let a = minStack.peek(), let b = maxStack.peek() {
45
            return Double((a + b)) / 2.0
46
        }
47
        else if minStack.count > maxStack.count {
48
            return Double(minStack.peek() ?? 0)
49
        }
50
        else if maxStack.count > minStack.count {
51
            return Double(maxStack.peek() ?? 0)
52
        }
53
        return 0
54
    }
55
}
56

57
let obj = MedianFinder()
58
obj.addNum(-1)
59
obj.addNum(-2)
60
obj.addNum(-3)
61
obj.addNum(-4)
62
obj.addNum(-5)
63
obj.addNum(6)
64

65
let ret_2: Double = obj.findMedian()

1
import Foundation
2

3
public struct SwiftPriorityQueue<Element> {
4
    private let _hasHigherPriority: (Element, Element) -> Bool
5
    private let _isEqual: (Element, Element) -> Bool
6

7
    private var _elements = [Element]()
8

9
    public init(hasHigherPriority: @escaping (Element, Element) -> Bool, isEqual: @escaping (Element, Element) -> Bool) {
10
        _hasHigherPriority = hasHigherPriority
11
        _isEqual = isEqual
12
    }
13

14
    public mutating func enqueue(_ element: Element) {
15
        _elements.append(element)
16
        bubbleToHigherPriority(_elements.count - 1)
17
    }
18

19
    public func peek() -> Element? {
20
        return _elements.first
21
    }
22

23
    public func array() -> [Element] {
24
        return _elements
25
    }
26

27
    public var isEmpty: Bool {
28
        return _elements.count == 0
29
    }
30

31
    public var count: Int {
32
        return _elements.count
33
    }
34

35
    public mutating func dequeue() -> Element? {
36
        guard let front = peek() else {
37
            return nil
38
        }
39

40
        removeAt(0)
41

42
        return front
43
    }
44

45
    public mutating func remove(_ element: Element) {
46
        for i in 0 ..< _elements.count {
47
            if _isEqual(_elements[i], element) {
48
                removeAt(i)
49
                return
50
            }
51
        }
52
    }
53

54
    private mutating func removeAt(_ index: Int) {
55
        let removingLast = index == _elements.count - 1
56
        if !removingLast {
57
            _elements.swapAt(index, _elements.count - 1)
58
        }
59

60
        _ = _elements.popLast()
61

62
        if !removingLast {
63
            bubbleToHigherPriority(index)
64
            bubbleToLowerPriority(index)
65
        }
66
    }
67

68
    private mutating func bubbleToHigherPriority(_ initialUnbalancedIndex: Int) {
69
        precondition(initialUnbalancedIndex >= 0)
70
        precondition(initialUnbalancedIndex < _elements.count)
71

72
        var unbalancedIndex = initialUnbalancedIndex
73

74
        while unbalancedIndex > 0 {
75
            let parentIndex = (unbalancedIndex - 1) / 2
76
            guard _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) else { break }
77
            _elements.swapAt(unbalancedIndex, parentIndex)
78
            unbalancedIndex = parentIndex
79
        }
80
    }
81

82
    private mutating func bubbleToLowerPriority(_ initialUnbalancedIndex: Int) {
83
        precondition(initialUnbalancedIndex >= 0)
84
        precondition(initialUnbalancedIndex < _elements.count)
85

86
        var unbalancedIndex = initialUnbalancedIndex
87
        while true {
88
            let leftChildIndex = unbalancedIndex * 2 + 1
89
            let rightChildIndex = unbalancedIndex * 2 + 2
90

91
            var highestPriorityIndex = unbalancedIndex
92

93
            if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
94
                highestPriorityIndex = leftChildIndex
95
            }
96

97
            if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
98
                highestPriorityIndex = rightChildIndex
99
            }
100

101
            guard highestPriorityIndex != unbalancedIndex else { break }
102
            _elements.swapAt(highestPriorityIndex, unbalancedIndex)
103

104
            unbalancedIndex = highestPriorityIndex
105
        }
106
    }
107
}
108

109
extension SwiftPriorityQueue : CustomDebugStringConvertible {
110
    public var debugDescription: String {
111
        return _elements.debugDescription
112
    }
113
}