★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/ ）➤GitHub地址：https://github.com/strengthen/LeetCode➤原文地址：https://www.cnblogs.com/strengthen/p/10478909.html ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
上代码：
1 /* Binary Heap Type */ 2 3 open class BinaryHeap< Type > 4 { 5 /* Heap Array */ 6 private var heapArray: [ Type ] 7 8 /* In Order Function */ 9 private let inOrder: ( _ a: Type, _ b: Type ) -> Bool 10 11 /* Initializer */ 12 13 public init( _ inOrder: @escaping ( _ a: Type, _ b: Type ) -> Bool ) 14 { 15 self.heapArray = [ Type ]() 16 self.inOrder = inOrder 17 } 18 19 /* Get Size */ 20 21 open func getSize() -> Int 22 { 23 return ( heapArray.count ) 24 } 25 26 /* Get Tale */ 27 28 private func getTale() -> Int 29 { 30 return ( heapArray.count - 1 ) 31 } 32 33 /* Get Parent */ 34 35 private func getParent( _ nodePosition: Int ) -> Int? 36 { 37 if nodePosition <= 0 38 { 39 return nil 40 } 41 let parentPosition: Int = ( ( nodePosition - 1 ) / 2 ) 42 return parentPosition 43 } 44 45 /* Get Left Child */ 46 47 private func getLeftChild( _ nodePosition: Int ) -> Int? 48 { 49 let childPosition = ( nodePosition * 2 ) + 1 50 if childPosition <= getTale() 51 { 52 return childPosition 53 } 54 else 55 { 56 return nil 57 } 58 } 59 60 /* Get Right Child */ 61 62 private func getRightChild( _ nodePosition: Int ) -> Int? 63 { 64 let childPosition = ( nodePosition * 2 ) + 2 65 if childPosition <= getTale() 66 { 67 return childPosition 68 } 69 else 70 { 71 return nil 72 } 73 } 74 75 /* Insert Element */ 76 77 open func insertElement( _ element: Type ) 78 { 79 heapArray.append( element ) 80 var traversal1 = getTale() 81 var goingUp = true 82 while goingUp 83 { 84 if let parent = getParent( traversal1 ) 85 { 86 if( !inOrder( heapArray[ parent ], heapArray[ traversal1 ] ) ) 87 { 88 let temp = heapArray[ traversal1 ] 89 heapArray[ traversal1 ] = heapArray[ parent ] 90 heapArray[ parent ] = temp 91 traversal1 = parent 92 } 93 else 94 { 95 goingUp = false 96 } 97 } 98 else 99 { 100 goingUp = false 101 } 102 } 103 } 104 105 /* Get Top Element */ 106 open func getTopElement() -> Type? 107 { 108 if getSize() == 0 109 { 110 return nil 111 } 112 else 113 { 114 return heapArray[ 0 ] 115 } 116 } 117 118 /* Delete Top Element */ 119 open func deleteTopElement() -> Type? 120 { 121 if getSize() == 0 122 { 123 return nil 124 } 125 let value = getTopElement() 126 heapArray[ 0 ] = heapArray[ getTale() ] 127 heapArray.removeLast() 128 129 if( getSize() > 1 ) 130 { 131 var traversal = 0 132 var goingDown = true 133 134 while( goingDown ) 135 { 136 var topChild: Int? = nil 137 if let child = getLeftChild( traversal ) 138 { 139 topChild = child 140 } 141 142 if let child = getRightChild( traversal ) 143 { 144 if( topChild == nil || !inOrder( heapArray[ topChild! ], heapArray[ child ] ) ) 145 { 146 topChild = child 147 } 148 } 149 150 if( topChild != nil && !inOrder( heapArray[ traversal ], heapArray[ topChild! ] ) ) 151 { 152 let temp = heapArray[ traversal ] 153 heapArray[ traversal ] = heapArray[ topChild! ] 154 heapArray[ topChild! ] = temp 155 156 traversal = topChild! 157 } 158 else 159 { 160 goingDown = false 161 } 162 } 163 } 164 return value 165 } 166 } 167 168 /* Array Traversal Type */ 169 170 class ArrayTraversal 171 { 172 private let array: [ Int ] 173 private var currentIndex: Int 174 175 private(set) var currentValue: Int 176 177 init( _ array: [ Int ] ) 178 { 179 self.array = array 180 self.currentIndex = 0 181 182 self.currentValue = array[ currentIndex ] 183 } 184 185 func getNextValue() -> Bool 186 { 187 if currentIndex == ( array.count - 1 ) 188 { 189 return false 190 } 191 currentIndex += 1 192 currentValue = array[ currentIndex ] 193 194 return true 195 } 196 }
转载于:https://www.cnblogs.com/strengthen/p/10478909.html
