introduce

A binary heap is a complete binary tree. The condition of a complete binary tree is that all levels need to be filled except the lowest level.

In practical use, binary heap can:

  • It’s easy to find a maximum or minimum in a set;
  • Applied to heap sort;
  • Build a priority queue;
  • Build some graphical algorithms.

It has the following two types:

  • Maximum heap, the higher the priority, the greater the value;
  • Minimum heap, the higher the priority, the smaller the value.

The maximum heap

The maximum heap, as shown above, has the following properties

  • The value of the parent is greater than or equal to the value of the child;
  • The root node has the maximum value.

The minimum heap

The smallest heap, shown above, has the following properties

  • The value of the parent node is less than or equal to that of the child node;
  • The root node has the smallest value.

implementation

Basic code

Struct Heap<Element: Equatable> {struct Heap<Element: Equatable> {var elements: [Element] = []; Let sort: (Element, Element) -> Bool init(sort: @escaping (Element, Element) -> Bool) { self.sort = sort } init(sort: @escaping (Element, Element) -> Bool, elements: [Element] = []) { self.sort = sort self.elements = elements if ! elements.isEmpty { for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) { siftDown(from: i) } } } }Copy the code

The data structure inside the binary heap looks like this:

Var elements: [Element] = [] var elements: [Element] = []

elements = [20 10 16 8 5 9 7 1]

Then you can express the view like this:

Level 1:20 Level 2:1016 Level 3:859 7 Level 4:1

So if an array is used to store binary heap data, the binary heap implementation can have:

    var isEmpty: Bool {
        elements.isEmpty
    }
    
    var count: Int {
        elements.count
    }
    
    func peek() -> Element? {
        elements.first
    }
    
    func leftChildIndex(ofParentAt index: Int) -> Int {
        (2 * index) + 1
    }
    
    func rightChildIndex(ofParentAt index: Int) -> Int {
        (2 * index) + 2
    }
    
    func parentIndex(ofChildAt index: Int) -> Int {
        (index - 1) / 2
    }
Copy the code

Removing the root Node

For maximum heap removal:

Replace the root node with the last node, swap the first and last element in the array variable of the binary heap, and remove the last element of the swapped array.

The same is true for minimum heap removal:

Of course, regardless of whether the maximum heap or the minimum heap is removed, the binary heap must satisfy the condition that it is a maximum heap or a minimum heap. In this case, the binary heap needs to be moved down from the root node to satisfy the condition.

Code implementation:

extension Heap { mutating func remove() -> Element? { guard ! Module.swapat (0, count-1) defer {// Start from the root and move down, SiftDown (from: 0)} return elements. RemoveLast ()} mutating func siftDown(from index: Int) { var parent = index while true { let left = leftChildIndex(ofParentAt: parent) let right = rightChildIndex(ofParentAt: If elements[left] > elements[candidate], the child node is larger than the parent node. If elements[left] > elements[candidate], the child node is larger than the parent node. Elements [left] < elements[candidate] if left < count && sort(elements[left], elements[candidate]) { candidate = left } if right < count && sort(elements[right], Elements [candidate]) {candidate = right} // If there is no movement, the parent node is greater than or equal to the child node, If candidate == parent {return} // replace elements. SwapAt (parent, candidate) // Parent = candidate}}} Parent = candidate}}Copy the code

The time complexity of the removal operation is order log N.

Remove any subscripts

Code implementation:

extension Heap { mutating func remove(at index: Int) -> Element? { guard index < elements.count else { return nil } if index == elements.count - 1 { return elements.removeLast() } else Elements. SwapAt (index, elements. Count -1) defer {// If necessary, siftDown(from: SiftUp (from: index)} return elements. RemoveLast ()}}Copy the code

Why siftDown(from: index)?

If node 3 is to be removed, after the position replacement of node 10 and node 3 at this time, the position replacement of node 10 and node 5 should be moved down to meet the minimum binary heap condition

Why siftUp(from: index)?

If node 8 is to be removed, then after the position replacement of node 12 and node 8, the position replacement of node 12 and node 10 should be moved up to meet the condition of maximum binary heap

Insert data into

To add a node to the binary heap, the actual operation is to add the node value to the array, at the end of the array, for the binary heap, at this point, we need to compare the size of the parent node to which the node is being added. If it is the maximum heap, then if the value added is less than or equal to the value of the parent node, then do not move, if it is greater than the value of the parent node, then the child node needs to move up, so that it meets the criteria of binary heap (minimum heap is less than the parent node needs to move up).

Extension Heap {mutating func insert(_ element: element) {// Start adding elements to the end of the array. Append (element) siftUp(from: elements.count - 1) } mutating func siftUp(from index: Int) { var child = index var parent = parentIndex(ofChildAt: // If the current node is larger than the parent node, then the position is replaced; If it's the minimum heap, if the current node is smaller than the sub node, While child > 0 && sort(elements[child], elements[parent]) {elements. SwapAt (child, parent) child = parent parent = parentIndex(ofChildAt: child) } } }Copy the code

The time complexity of the insert operation is order log n.

search

Since the data store at the bottom uses an array, a simple implementation would be to traverse the entire array in order n time. The following is a binary heap search optimization implementation:

extension Heap { func index(of element: Element, startingAt i: Int) -> Int? { if i >= count { return nil } if sort(element, Elements [I]) {return nil} if element == elements[I] {return I} if let j = index(of: element, startingAt: LeftChildIndex (ofParentAt: I) {return j} if let j = index(of: element, startingAt: rightChildIndex(ofParentAt: i)) { return j } return nil } }Copy the code

Time complexity O(n)

test

Var heap = heap (sort: >, elements: [1, 23, 34, 3, 43, 32, 3, 44, 442]) print(heap.elements) print("\n: \n") while! heap.isEmpty { print(heap.remove()!) }Copy the code

Output:

[442, 44, 34, 23, 43, 32, 3, 1, 3] Start removing: 442 44 43 34 32 23 3 3 1Copy the code