SHARE
TWEET

Untitled

a guest Aug 20th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import Foundation
  2. public struct Heap<T> {
  3.    
  4.     private var nodes = [T]()
  5.    
  6.     private var orderCriteria: (T, T) -> Bool
  7.    
  8.     public init(sort: @escaping (T, T) -> Bool) {
  9.         self.orderCriteria = sort
  10.     }
  11.    
  12.     public init(array: [T], sort: @escaping (T, T) -> Bool) {
  13.         self.orderCriteria = sort
  14.         configureHeap(from: array)
  15.     }
  16.    
  17.     private mutating func configureHeap(from array: [T]) {
  18.         nodes = array
  19.         for i in (0...(nodes.count/2-1)).reversed() {
  20.             shiftDown(i)
  21.         }
  22.     }
  23.    
  24.     public var isEmpty: Bool {
  25.         return nodes.isEmpty
  26.     }
  27.    
  28.     public var count: Int {
  29.         return nodes.count
  30.     }
  31.    
  32.     @inline(__always) private func parentIndex(of index: Int) -> Int {
  33.         return (index - 1) / 2
  34.     }
  35.    
  36.     @inline(__always) private func leftIndex(of index: Int) -> Int {
  37.         return index * 2 + 1
  38.     }
  39.    
  40.     @inline(__always) private func rightIndex(of index: Int) -> Int {
  41.         return index * 2 + 2
  42.     }
  43.    
  44.     public func peek() -> T? {
  45.         return nodes.first
  46.     }
  47.    
  48.     public mutating func insert(_ value: T) {
  49.         nodes.append(value)
  50.         shiftUp(nodes.count-1)
  51.     }
  52.    
  53.     public mutating func insert<S: Sequence>(_ s: S) where S.Element == T {
  54.         for value in s {
  55.             insert(value)
  56.         }
  57.     }
  58.    
  59.    
  60.     @discardableResult
  61.     public mutating func remove() -> T? {
  62.         guard !nodes.isEmpty else {
  63.             return nil
  64.         }
  65.         if nodes.count == 1 {
  66.             return nodes.removeLast()
  67.         } else {
  68.             // use the last node the replace the first and shift down from the first
  69.             let value = nodes[0]
  70.             nodes[0] = nodes.removeLast()
  71.             shiftDown(0)
  72.             return value
  73.         }
  74.     }
  75.    
  76.     fileprivate mutating func replace(index i: Int, value: T) {
  77.         guard i < nodes.count else { return }
  78.         remove(at: i)
  79.         insert(value)
  80.     }
  81.    
  82.     @discardableResult public mutating func remove(at index: Int) -> T? {
  83.         guard index < nodes.count else {
  84.             return nil
  85.         }
  86.        
  87.         let size = nodes.count - 1
  88.         if index != size {
  89.             nodes.swapAt(index, size)
  90.             shiftDown(from: index, until: size)
  91.             shiftUp(index)
  92.         }
  93.         return nodes.removeLast()
  94.     }
  95.    
  96.     private mutating func shiftUp(_ index: Int) {
  97.        
  98.         var childIndex = index
  99.         let child = nodes[childIndex]
  100.         var parentIndex = self.parentIndex(of: index)
  101.         while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
  102.             nodes[childIndex] = nodes[parentIndex]
  103.             childIndex = parentIndex
  104.             parentIndex = self.parentIndex(of: childIndex)
  105.         }
  106.        
  107.         nodes[childIndex] = child
  108.     }
  109.    
  110.     private mutating func shiftDown(from index: Int, until endIndex: Int) {
  111.         let leftChildIndex = leftIndex(of: index)
  112.         let rightChildIndex = leftChildIndex + 1
  113.         var first = index
  114.         if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
  115.             first = leftChildIndex
  116.         }
  117.         if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
  118.             first = rightChildIndex
  119.         }
  120.         if first == index {
  121.             return
  122.         }
  123.         nodes.swapAt(index, first)
  124.         shiftDown(from: first, until: endIndex)
  125.     }
  126.    
  127.    
  128.     private mutating func shiftDown(_ index: Int) {
  129.         shiftDown(from: index, until: nodes.count)
  130.     }
  131. }
  132.  
  133. extension Heap {
  134.     public mutating func sort() -> [T] {
  135.         for i in stride(from: (nodes.count - 1), through: 1, by: -1) {
  136.             nodes.swapAt(0, i)
  137.             shiftDown(from: 0, until: i)
  138.         }
  139.         return nodes
  140.     }
  141. }
  142.  
  143. public func heapsort<T>(_ a: [T], _ sort: @escaping (T, T) -> Bool) -> [T] {
  144.     let reverseOrder = { i1, i2 in sort(i2, i1) }
  145.     var h = Heap(array: a, sort: reverseOrder)
  146.     return h.sort()
  147. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top