如何在 Swift 中使用最小堆实现 PriorityQueue？

Question

首先，Swift标准库中有没有内置类似"PriorityQueue"的class？找不到了，就自己写了。

当我从队列中弹出项目时，我希望该项目目前是最小的。对于大多数项目来说，这是正确的，但其中一些（很少）没有放在正确的位置，我似乎无法找出原因。可以在 Playground 和运行（包括测试）中复制粘贴以下代码片段。

class PriorityQueue<T> {
    private var arr: [T] = []
    private let compare: (_ a: T, _ b: T) -> Bool

    init(_ compare: @escaping (_ a: T, _ b: T) -> Bool) {
        self.compare = compare
    }

    func insert(_ a: T) {
        arr.insert(a, at: 0)
        heapify(0)
    }

    func pop() -> 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 < arr.count, compare(arr[l], arr[smallest]) {
            smallest = l
        }

        if r < 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<Int> = PriorityQueue { [=11=] <  }

for i in 0..<size {
    arr[i] = Int.random(in: 1...10000)
    queue.insert(arr[i])
}

let sorted: [Int] = arr.sorted()
for i in 0..<size {
    let n: Int = queue.pop() ?? 0
    print(n, sorted[i], n == sorted[i])
}

95% 的时间，项目以正确的顺序从队列中弹出，但偶尔，我会得到这样的结果：

579 579 真

1372 1372 真

1762 1762 真

2113 2113 真

2332 2332 真

2562 2418 假

2701 2562 假

3137 2701 假

2418 3137 假

4615 4615 真

6085 6085 真

6820 6820 真

7382 7382 真

8878 8878 真

9220 9220 真

Answer 1

我刚刚弄清楚为什么我错了，错误发生在 func insert(_ a: T)，我只是在前面加上新元素，然后尝试从第一个元素堆化数组。

函数应该重写：

func insert(_ a: T) {
    arr.append(a)
    for i in stride(from: arr.count / 2 - 1, through: 0, by: -1) {
        heapify(i)
    }
}

但是，这不是很有效，因为我们正在破坏整个堆化数组并重新堆化大部分堆化的内容。因此，我不是在元素前面添加元素，而是附加它，这样，我们最多会破坏堆的一个子树。从那里，我们尝试从下到上堆化数组：

private func heapifyUp(_ i: Int) {
    if i == 0 {
        return
    }

    let parent: Int, sibling: Int
    if i.isMultiple(of: 2) {
        parent = (i - 2) / 2
        sibling = parent * 2 + 1
    } else {
        parent = (i - 1) / 2
        sibling = parent * 2 + 2
    }

    var smallest: Int = parent

    if compare(arr[i], arr[smallest]) {
        smallest = i
    }

    if sibling < arr.count, compare(arr[sibling], arr[smallest]) {
        smallest = sibling
    }

    if smallest == parent {
        return
    }

    let temp: T = arr[parent]
    arr[parent] = arr[smallest]
    arr[smallest] = temp

    heapifyUp(parent)
    heapify(smallest)
}

我犯的错误是我假设在我添加一个元素之前，数组的其余部分（除了新元素）仍然是堆化的，这是不正确的。考虑这种情况：

您有一个堆化数组：[5, 8, 6, 9, 12, 7]，当您添加一个新元素 10 并调用 heapify(0) 时，数组变为：[5, 6, 8 , 10, 9, 12, 7]，其中8是12和7的父级，但8不小于7.

Answer 2

向二叉堆中添加一个项目非常简单。您将该项目追加到数组的末尾，并将其从堆中冒泡到适当的位置。我不知道Swift，所以我给你伪代码。假设支持数组（或列表）被称为 arr:

insert (val)
    append val to arr
    i = arr.count - 1
    while (i > 0)
        parent = (i-1)/2
        if (arr[i] < arr[parent])
            swap(arr[i], arr[parent])
            i = parent
        else
            break

Answer 3

我会考虑这样写这个 heapifyUp：

mutating private func heapifyUp(_ index: Int) {
    var childIndex = index
    let child = items[childIndex]
    var parentIndex = getParentIndex(childIndex)

    while childIndex > 0 && orderCriteria(child, items[parentIndex]) {
        items[childIndex] = items[parentIndex]
        childIndex = parentIndex
        parentIndex = getParentIndex(childIndex)
    }

    items[childIndex] = child
}

orderCriteria 就是：

private var orderCriteria: (T, T) -> Bool

您可以这样初始化您的堆：

public init(sort: @escaping (T, T) -> Bool) {
    self.orderCriteria = sort
}

这样您就可以通过定义 orderCriteria 将其用作 MinHeap 或 MaxHeap。

您的 insert/add 函数变为：

mutating public func add(_ item: T) {
    items.append(item)
    heapifyUp(items.count - 1)
}

希望对您有所帮助！我认为您的解决方案也非常相似。请注意，我使用的 items 是您的 arr 并且您的 heapify() 函数似乎也可以正常工作，但我的是迭代版本而您的是递归版本。老实说，虽然我没有测试过你的。

如何在 Swift 中使用最小堆实现 PriorityQueue？

How to implement PriorityQueue using min-heap in Swift?

algorithm

heap

priority-queue

swift