mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
398 lines
13 KiB
Swift
398 lines
13 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 2021 - 2026 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
// SPDX-License-Identifier: Apache-2.0 WITH Swift-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
|
|
/// A container type implementing a double-ended priority queue.
|
|
/// `Heap` is a container of `Comparable` elements that provides immediate
|
|
/// access to its minimal and maximal members, and supports removing these items
|
|
/// or inserting arbitrary new items in (amortized) logarithmic complexity.
|
|
///
|
|
/// var queue: Heap<Int> = [3, 4, 1, 2]
|
|
/// queue.insert(0)
|
|
/// print(queue.min) // 0
|
|
/// print(queue.popMax()) // 4
|
|
/// print(queue.max) // 3
|
|
///
|
|
/// `Heap` implements the min-max heap data structure, based on
|
|
/// [Atkinson et al. 1986].
|
|
///
|
|
/// [Atkinson et al. 1986]: https://doi.org/10.1145/6617.6621
|
|
///
|
|
/// > M.D. Atkinson, J.-R. Sack, N. Santoro, T. Strothotte.
|
|
/// "Min-Max Heaps and Generalized Priority Queues."
|
|
/// *Communications of the ACM*, vol. 29, no. 10, Oct. 1986., pp. 996-1000,
|
|
/// doi:[10.1145/6617.6621](https://doi.org/10.1145/6617.6621)
|
|
///
|
|
/// To efficiently implement these operations, a min-max heap arranges its items
|
|
/// into a complete binary tree, maintaining a specific invariant across levels,
|
|
/// called the "min-max heap property": each node at an even level in the tree
|
|
/// must be less than or equal to all its descendants, while each node at an odd
|
|
/// level in the tree must be greater than or equal to all of its descendants.
|
|
/// To achieve a compact representation, this tree is stored in breadth-first
|
|
/// order inside a single contiguous array value.
|
|
///
|
|
/// Unlike most container types, `Heap` doesn't provide a direct way to iterate
|
|
/// over the elements it contains -- it isn't a `Sequence` (nor a `Collection`).
|
|
/// This is because the order of items in a heap is unspecified and unstable:
|
|
/// it may vary between heaps that contain the same set of items, and it may
|
|
/// sometimes change in between versions of this library. In particular, the
|
|
/// items are (almost) never expected to be in sorted order.
|
|
///
|
|
/// For cases where you do need to access the contents of a heap directly and
|
|
/// you don't care about their (lack of) order, you can do so by invoking the
|
|
/// `unordered` view. This read-only view gives you direct access to the
|
|
/// underlying array value:
|
|
///
|
|
/// for item in queue.unordered {
|
|
/// ...
|
|
/// }
|
|
///
|
|
/// The name `unordered` highlights the lack of ordering guarantees on the
|
|
/// contents, and it helps avoid relying on any particular order.
|
|
@frozen
|
|
public struct Heap<Element: Comparable> {
|
|
@usableFromInline
|
|
internal var _storage: ContiguousArray<Element>
|
|
|
|
/// Creates an empty heap.
|
|
@inlinable
|
|
public init() {
|
|
_storage = []
|
|
}
|
|
}
|
|
|
|
extension Heap: Sendable where Element: Sendable {}
|
|
|
|
extension Heap {
|
|
/// A Boolean value indicating whether or not the heap is empty.
|
|
///
|
|
/// - Complexity: O(1)
|
|
@inlinable @inline(__always)
|
|
public var isEmpty: Bool {
|
|
_storage.isEmpty
|
|
}
|
|
|
|
/// The number of elements in the heap.
|
|
///
|
|
/// - Complexity: O(1)
|
|
@inlinable @inline(__always)
|
|
public var count: Int {
|
|
_storage.count
|
|
}
|
|
|
|
/// A read-only view into the underlying array.
|
|
///
|
|
/// Note: The elements aren't _arbitrarily_ ordered (it is, after all, a
|
|
/// heap). However, no guarantees are given as to the ordering of the elements
|
|
/// or that this won't change in future versions of the library.
|
|
///
|
|
/// - Complexity: O(1)
|
|
@inlinable
|
|
public var unordered: [Element] {
|
|
Array(_storage)
|
|
}
|
|
|
|
/// Creates an empty heap with preallocated space for at least the
|
|
/// specified number of elements.
|
|
///
|
|
/// Use this initializer to avoid intermediate reallocations of a heap's
|
|
/// storage when you know in advance how many elements you'll insert into it
|
|
/// after creation.
|
|
///
|
|
/// - Parameter minimumCapacity: The minimum number of elements that the newly
|
|
/// created heap should be able to store without reallocating its storage.
|
|
///
|
|
/// - Complexity: O(1) allocations
|
|
@inlinable
|
|
public init(minimumCapacity: Int) {
|
|
self.init()
|
|
self.reserveCapacity(minimumCapacity)
|
|
}
|
|
|
|
/// Reserves enough space to store the specified number of elements.
|
|
///
|
|
/// If you are adding a known number of elements to a heap, use this method
|
|
/// to avoid multiple reallocations. This method ensures that the heap has
|
|
/// unique, mutable, contiguous storage, with space allocated for at least
|
|
/// the requested number of elements.
|
|
///
|
|
/// For performance reasons, the size of the newly allocated storage might be
|
|
/// greater than the requested capacity.
|
|
///
|
|
/// - Parameter minimumCapacity: The minimum number of elements that the
|
|
/// resulting heap should be able to store without reallocating its storage.
|
|
///
|
|
/// - Complexity: O(`count`)
|
|
@inlinable
|
|
public mutating func reserveCapacity(_ minimumCapacity: Int) {
|
|
_storage.reserveCapacity(minimumCapacity)
|
|
}
|
|
|
|
/// Inserts the given element into the heap.
|
|
///
|
|
/// - Complexity: O(log(`count`)) element comparisons
|
|
@inlinable
|
|
public mutating func insert(_ element: Element) {
|
|
_storage.append(element)
|
|
|
|
unsafe _update { handle in
|
|
unsafe handle.bubbleUp(_HeapNode(offset: handle.count - 1))
|
|
}
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Returns the element with the lowest priority, if available.
|
|
///
|
|
/// - Complexity: O(1)
|
|
@inlinable
|
|
public var min: Element? {
|
|
_storage.first
|
|
}
|
|
|
|
/// Returns the element with the highest priority, if available.
|
|
///
|
|
/// - Complexity: O(1)
|
|
@inlinable
|
|
public var max: Element? {
|
|
_storage.withUnsafeBufferPointer { buffer in
|
|
guard buffer.count > 2 else {
|
|
// If count is 0, `last` will return `nil`
|
|
// If count is 1, the last (and only) item is the max
|
|
// If count is 2, the last item is the max (as it's the only item in the
|
|
// first max level)
|
|
return unsafe buffer.last
|
|
}
|
|
// We have at least 3 items -- return the larger of the two in the first
|
|
// max level
|
|
return unsafe Swift.max(buffer[1], buffer[2])
|
|
}
|
|
}
|
|
|
|
/// Removes and returns the element with the lowest priority, if available.
|
|
///
|
|
/// - Complexity: O(log(`count`)) element comparisons
|
|
@inlinable
|
|
public mutating func popMin() -> Element? {
|
|
guard _storage.count > 0 else { return nil }
|
|
|
|
var removed = _storage.removeLast()
|
|
|
|
if _storage.count > 0 {
|
|
unsafe _update { handle in
|
|
let minNode = _HeapNode.root
|
|
unsafe handle.swapAt(minNode, with: &removed)
|
|
unsafe handle.trickleDownMin(minNode)
|
|
}
|
|
}
|
|
|
|
_checkInvariants()
|
|
return removed
|
|
}
|
|
|
|
/// Removes and returns the element with the highest priority, if available.
|
|
///
|
|
/// - Complexity: O(log(`count`)) element comparisons
|
|
@inlinable
|
|
public mutating func popMax() -> Element? {
|
|
guard _storage.count > 2 else { return _storage.popLast() }
|
|
|
|
var removed = _storage.removeLast()
|
|
|
|
unsafe _update { handle in
|
|
if handle.count == 2 {
|
|
if unsafe handle[.leftMax] > removed {
|
|
unsafe handle.swapAt(.leftMax, with: &removed)
|
|
}
|
|
} else {
|
|
let maxNode = unsafe handle.maxValue(.leftMax, .rightMax)
|
|
unsafe handle.swapAt(maxNode, with: &removed)
|
|
unsafe handle.trickleDownMax(maxNode)
|
|
}
|
|
}
|
|
|
|
_checkInvariants()
|
|
return removed
|
|
}
|
|
|
|
/// Removes and returns the element with the lowest priority.
|
|
///
|
|
/// The heap *must not* be empty.
|
|
///
|
|
/// - Complexity: O(log(`count`)) element comparisons
|
|
@inlinable
|
|
@discardableResult
|
|
public mutating func removeMin() -> Element {
|
|
return popMin()!
|
|
}
|
|
|
|
/// Removes and returns the element with the highest priority.
|
|
///
|
|
/// The heap *must not* be empty.
|
|
///
|
|
/// - Complexity: O(log(`count`)) element comparisons
|
|
@inlinable
|
|
@discardableResult
|
|
public mutating func removeMax() -> Element {
|
|
return popMax()!
|
|
}
|
|
|
|
/// Replaces the minimum value in the heap with the given replacement,
|
|
/// then updates heap contents to reflect the change.
|
|
///
|
|
/// The heap must not be empty.
|
|
///
|
|
/// - Parameter replacement: The value that is to replace the current
|
|
/// minimum value.
|
|
/// - Returns: The original minimum value before the replacement.
|
|
///
|
|
/// - Complexity: O(log(`count`)) element comparisons
|
|
@inlinable
|
|
@discardableResult
|
|
public mutating func replaceMin(with replacement: Element) -> Element {
|
|
precondition(!isEmpty, "No element to replace")
|
|
|
|
var removed = replacement
|
|
unsafe _update { handle in
|
|
let minNode = _HeapNode.root
|
|
unsafe handle.swapAt(minNode, with: &removed)
|
|
unsafe handle.trickleDownMin(minNode)
|
|
}
|
|
_checkInvariants()
|
|
return removed
|
|
}
|
|
|
|
/// Removes all the elements that satisfy the given predicate.
|
|
///
|
|
/// - Parameter shouldBeRemoved: A closure that takes an element of the
|
|
/// heap as its argument and returns a Boolean value indicating
|
|
/// whether the element should be removed from the heap.
|
|
///
|
|
/// - Complexity: O(*n*), where *n* is the number of items in the heap.
|
|
@inlinable
|
|
public mutating func removeAll(
|
|
where shouldBeRemoved: (Element) throws -> Bool
|
|
) rethrows {
|
|
defer {
|
|
if _storage.count > 1 {
|
|
unsafe _update { handle in
|
|
unsafe handle.heapify()
|
|
}
|
|
}
|
|
_checkInvariants()
|
|
}
|
|
try _storage.removeAll(where: shouldBeRemoved)
|
|
}
|
|
|
|
/// Replaces the maximum value in the heap with the given replacement,
|
|
/// then updates heap contents to reflect the change.
|
|
///
|
|
/// The heap must not be empty.
|
|
///
|
|
/// - Parameter replacement: The value that is to replace the current maximum
|
|
/// value.
|
|
/// - Returns: The original maximum value before the replacement.
|
|
///
|
|
/// - Complexity: O(log(`count`)) element comparisons
|
|
@inlinable
|
|
@discardableResult
|
|
public mutating func replaceMax(with replacement: Element) -> Element {
|
|
precondition(!isEmpty, "No element to replace")
|
|
|
|
var removed = replacement
|
|
unsafe _update { handle in
|
|
switch handle.count {
|
|
case 1:
|
|
unsafe handle.swapAt(.root, with: &removed)
|
|
case 2:
|
|
unsafe handle.swapAt(.leftMax, with: &removed)
|
|
unsafe handle.bubbleUp(.leftMax)
|
|
default:
|
|
let maxNode = unsafe handle.maxValue(.leftMax, .rightMax)
|
|
unsafe handle.swapAt(maxNode, with: &removed)
|
|
unsafe handle.bubbleUp(maxNode) // This must happen first
|
|
unsafe handle.trickleDownMax(maxNode) // Either new element or dethroned min
|
|
}
|
|
}
|
|
_checkInvariants()
|
|
return removed
|
|
}
|
|
}
|
|
|
|
// MARK: -
|
|
|
|
extension Heap {
|
|
/// Initializes a heap from a sequence.
|
|
///
|
|
/// - Complexity: O(*n*), where *n* is the number of items in `elements`.
|
|
@inlinable
|
|
public init(_ elements: some Sequence<Element>) {
|
|
_storage = ContiguousArray(elements)
|
|
guard _storage.count > 1 else { return }
|
|
|
|
unsafe _update { handle in
|
|
unsafe handle.heapify()
|
|
}
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Inserts the elements in the given sequence into the heap.
|
|
///
|
|
/// - Parameter newElements: The new elements to insert into the heap.
|
|
///
|
|
/// - Complexity: O(`count` + *k*), where *k* is the length of `newElements`.
|
|
@inlinable
|
|
public mutating func insert(
|
|
contentsOf newElements: some Sequence<Element>
|
|
) {
|
|
let origCount = self.count
|
|
if origCount == 0 {
|
|
self = Self(newElements)
|
|
return
|
|
}
|
|
defer { _checkInvariants() }
|
|
_storage.append(contentsOf: newElements)
|
|
let newCount = self.count
|
|
|
|
guard newCount > origCount, newCount > 1 else {
|
|
// If we didn't append, or the result is too small to violate heapness,
|
|
// then we have nothing else to do.
|
|
return
|
|
}
|
|
|
|
// Otherwise we can either insert items one by one, or we can run Floyd's
|
|
// algorithm to re-heapify our entire storage from scratch.
|
|
//
|
|
// If n is the original count, and k is the number of items we need to
|
|
// append, then Floyd's costs O(n + k) comparisons/swaps, while
|
|
// the naive loop costs k * log(n + k) -- so we expect that Floyd will
|
|
// be cheaper whenever k is "large enough" relative to n.
|
|
//
|
|
// Floyd's algorithm has a worst-case upper complexity bound of 2 * (n + k),
|
|
// so one simple heuristic is to use it whenever k * log(n + k) exceeds
|
|
// that.
|
|
//
|
|
// FIXME: Write a benchmark to verify this heuristic.
|
|
let heuristicLimit = 2 &* newCount / newCount._binaryLogarithm()
|
|
let useFloyd = (newCount - origCount) > heuristicLimit
|
|
unsafe _update { handle in
|
|
if useFloyd {
|
|
unsafe handle.heapify()
|
|
} else {
|
|
for offset in origCount ..< handle.count {
|
|
unsafe handle.bubbleUp(_HeapNode(offset: offset))
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|