我对堆数据结构有疑问。
我有三个公共职能。我无法设置正确的功能shiftUp和shiftDown。
在shiftUp中，我尝试比较堆中的元素并交换它们的
这是我的代码实现：
class Heap {
var heap: [Int]
init(array: [Int]) {
self.heap = array
}
var findMax: Int { return heap.first! }
private var count: Int {return heap.count}
private func floor() -> Int {
let floor = log2(Double(heap.count))
return Int(floor)
}
private func indexOf(element: Int) -> Int {
return heap.index(of: element)!
}
private func parentIndex(index: Int) -> Int {
return floor()*(index-1/2)
}
private func leftChildIndex(index: Int) -> Int {
return 2*index+1
}
private func rightChildIndex(index: Int) -> Int {
return 2*index+2
}
private func swapIfNeed(first: Int,second: Int) {
swap(&heap[indexOf(element: first)] , &heap[indexOf(element: second)])
}
func shiftDown(index: Int) {
let parent = heap[parentIndex(index: index)]
let leftChild = heap[leftChildIndex(index: index)]
let rightChild = heap[rightChildIndex(index: index)]
if parent <= leftChild {
swapIfNeed(first: parent, second: leftChild)
shiftDown(index: index+1)
} else if parent <= rightChild {
swapIfNeed(first: parent, second: rightChild)
shiftDown(index: index+1)
}
}
private func shiftUp() {}
func removeMax() {
}
func addElement(element: Int) {}
}
请在Swift 4中找到我对Heap DS的实现。
struct Heap<T: Comparable>{
private var heap = [T]()
mutating func insert(element: T){
heap.append(element)
var index = heap.count - 1
heapify(childIndex: index)
}
mutating func heapify(childIndex: Int){
var parentIndex = (childIndex - 1)/2
if parentIndex >= 0 {
if heap[parentIndex] < heap[childIndex] {
var tempElement = heap[parentIndex]
heap[parentIndex] = heap[childIndex]
heap[childIndex] = tempElement
heapify(childIndex: parentIndex)
}else{
print("Created valid heap")
}
}else{
print("No parent")
}
}
}
import Foundation
struct Heap<Element> where Element: Comparable {
// elements - collection where heap store values
private(set) var elements = [Element]()
// priority - description of order in a heap
let priority: Priority
init(priority: Priority) { self.priority = priority }
enum Priority {
case parentsGreaterThanOrEqualChildren
case parentsLessThanOrEqualChildren
func isCorrect(parentValue: Element, childValue: Element) -> Bool {
switch self {
case .parentsGreaterThanOrEqualChildren: return parentValue >= childValue
case .parentsLessThanOrEqualChildren: return parentValue <= childValue
}
}
}
}
// MARK: Init
extension Heap {
// Init heap from representing array means that array is already ordered to be as base of heap.
// If not - heap will be not created
init?(fromRepresenting array: [Element], priority: Priority) {
self.init(priority: priority)
elements = array
if array.count > 1 {
var index: Int!
var indicesQueue = [0]
indicesQueue.reserveCapacity(indicesQueue.count/2)
while !indicesQueue.isEmpty {
index = indicesQueue.popLast()
let childrenIndices = self.childrenIndices(ofParentAt: index)
if let childIndex = childrenIndices.left {
guard isPriorityCorrect(parentIndex: index, childIndex: childIndex) else { return nil }
indicesQueue.insert(childIndex, at: 0)
}
if let childIndex = childrenIndices.right {
guard isPriorityCorrect(parentIndex: index, childIndex: childIndex) else { return nil }
indicesQueue.insert(childIndex, at: 0)
}
}
index += 1
}
}
// Init heap by inserting elements from array means that elements in array will be reordered if needed
init(insertElementsFrom array: [Element], priority: Priority) {
self.init(priority: priority)
if array.isEmpty { return }
elements = array
for index in stride(from: count/2, through: 0, by: -1) {
siftDown(startAt: index)
}
}
// Check if the priority of the parent element higher than child element
private func isPriorityCorrect (parentIndex: Int, childIndex: Int) -> Bool {
priority.isCorrect(parentValue: elements[parentIndex], childValue: elements[childIndex])
}
private func isPriorityCorrect (parentValue: Element, childValue: Element) -> Bool {
priority.isCorrect(parentValue: parentValue, childValue: childValue)
}
}
// MARK: States
extension Heap {
// Get flag that heap is empty (has no values)
var isEmpty: Bool { elements.isEmpty }
// Get number of elements in heap
var count: Int { elements.count }
// Show element with max priority (first that will be removed)
func peek() -> Element? { elements.first }
}
// MARK: Get index
extension Heap {
// calculated property returns value(s) that do not check bounds of existing heap's collection (elements)
private func calculateParentIndex(childAt index: Int) -> Int { (index - 1) / 2 }
private func calculateChildrenIndices(ofParentAt index: Int) -> (left: Int, right: Int) {
let left = index * 2 + 1
return (left, left + 1)
}
// Check if range 0..<elements.count contains index
private func isValid(index: Int) -> Bool { 0 ..< count ~= index }
// Get parent's left and right indices. left and left indices can be nil (do not exist in current heap)
func childrenIndices(ofParentAt index: Int) -> (left: Int?, right: Int?) {
let indices = calculateChildrenIndices(ofParentAt: index)
return (isValid(index: indices.left) ? indices.left : nil,
isValid(index: indices.right) ? indices.right : nil)
}
// Get the parent index of the child
func parentIndex(childAt index: Int) -> Int? {
let index = calculateParentIndex(childAt: index)
if isValid(index: index) { return index }
return nil
}
}
// MARK: Sift - Reordering mechanism.
// Heap order - where each parent node has higher priority than the child nodes.
extension Heap {
// Traverse binary tree from parent node (index) to each child node.
// Swap elements if needed to order in heap.
private mutating func siftDown(startAt index: Int, stopAt count: Int? = nil) {
let count = count ?? self.count
var parentIndex = index
var childrenIndices: (left: Int, right: Int)
var swapDestinationIndex = index
while true {
childrenIndices = self.calculateChildrenIndices(ofParentAt: parentIndex)
swapDestinationIndex = parentIndex
if childrenIndices.left < count &&
isPriorityCorrect(parentIndex: childrenIndices.left, childIndex: parentIndex) {
swapDestinationIndex = childrenIndices.left
}
if childrenIndices.right < count &&
isPriorityCorrect(parentIndex: childrenIndices.right, childIndex: swapDestinationIndex) {
swapDestinationIndex = childrenIndices.right
}
guard parentIndex != swapDestinationIndex else { return }
elements.swapAt(parentIndex, swapDestinationIndex)
parentIndex = swapDestinationIndex
}
}
// Traverse binary tree from child node (index) to the head node of the tree.
// Swap elements if needed to order in heap.
private mutating func siftUp(startAt firstIndex: Int) {
var child = firstIndex
var parent = calculateParentIndex(childAt: firstIndex)
while child > 0 && isPriorityCorrect(parentIndex: child, childIndex: parent) {
elements.swapAt(child, parent)
child = parent
parent = calculateParentIndex(childAt: child)
}
}
}
// MARK: Insert/Remove
extension Heap {
// Insert new element in heap in correct position
mutating func insert(_ value: Element) {
elements.append(value)
siftUp(startAt: count - 1)
}
// Remove element with max priority (first in array "elements") and restore order (swap elements) if needed
@discardableResult
mutating func removeElementWithHighestPriority() -> Element? {
switch count {
case 0: return nil
case 1: return elements.removeLast()
default:
elements.swapAt(0, count - 1)
defer { siftDown(startAt: 0) }
return elements.removeLast()
}
}
// Remove element at specific index and restore order (swap elements) if needed
@discardableResult
mutating func remove(at index: Int) -> Element? {
guard isValid(index: index) else { return nil }
if index == count - 1 { return elements.removeLast() }
elements.swapAt(index, count-1)
defer {
siftDown(startAt: index)
siftUp(startAt: index)
}
return elements.removeLast()
}
}
// MARK: Exporting
extension Heap {
func representAsReversedSortedArray() -> [Element] {
var heap = self
for index in heap.elements.indices.reversed() {
heap.elements.swapAt(0, index)
heap.siftDown(startAt: 0, stopAt: index)
}
return heap.elements
}
}
// MARK: Search
extension Heap {
// Get first index of the element
func firstIndex(of element: Element, startAt index: Int = 0) -> Int? {
guard isValid(index: index),
isPriorityCorrect(parentValue: elements[index], childValue: element) else { return nil }
if elements[index] == element { return index }
let childrenIndices = self.calculateChildrenIndices(ofParentAt: index)
let left = firstIndex(of: element, startAt: childrenIndices.left)
let right = firstIndex(of: element, startAt: childrenIndices.right)
if let left = left, let right = right {return min(left, right) }
return left ?? right
}
}
// MARK: CustomStringConvertible & Debug info
extension Heap: CustomStringConvertible {
public var description: String { "\(elements)" }
// Get binary tree representation of the heap. Helpful for debugging
func getDiagram() -> String { diagram(forElementAt: 0) }
private func diagramSpacing() -> String { " " }
private func diagram(forElementAt index: Int?,
_ top: String = " ",
_ root: String = " ",
_ bottom: String = " ") -> String {
guard let index = index else { return "" }
let childrenIndices = self.childrenIndices(ofParentAt: index)
if childrenIndices.left == nil && childrenIndices.right == nil {
return root + " \(elements[index])\n"
}
var parentValueString: String!
if root == " " {
parentValueString = root + "\(elements[index])\n"
} else {
parentValueString = root + " \(elements[index])\n"
}
return diagram(forElementAt: childrenIndices.right,
top + " ",
top + "┌─",
top + "│ ") +
parentValueString +
diagram(forElementAt: childrenIndices.left,
bottom + "│ ",
bottom + "└─",
bottom + " ")
}
}
let array = [1, 2,3, 4,6,7,8, 32,44,113]
if let heap = Heap(fromRepresenting: array, priority: .parentsLessThanOrEqualChildren) {
//...
}
if let heap = Heap(fromRepresenting: array, priority: .parentsGreaterThanOrEqualChildren) {
//...
}
var heap = Heap<Int>(priority: .parentsLessThanOrEqualChildren)
heap = Heap(priority: .parentsGreaterThanOrEqualChildren)
heap = Heap(insertElementsFrom: array, priority: .parentsLessThanOrEqualChildren)
heap = Heap(insertElementsFrom: array, priority: .parentsGreaterThanOrEqualChildren)
print("elements: \(heap.elements)")
heap.insert(1)
print("remove: \(heap.removeElementWithHighestPriority())")
print("first index of 2: \(heap.firstIndex(of: 2))")
print("is empty: \(heap.isEmpty)")
print("count: \(heap.count)")
print("peek: \(heap.peek())")
print(heap.getDiagram())
elements: [113, 44, 8, 32, 6, 7, 3, 1, 4, 2]
remove: Optional(113)
first index of 2: Optional(9)
is empty: false
count: 10
peek: Optional(44)
┌─ 3
┌─ 8
│ └─ 7
44
│ ┌─ 6
│ │ └─ 2
└─ 32
│ ┌─ 1
└─ 4
└─ 1
import XCTest
@testable import stackoverflow_39876805
class HeapSpecificTests: XCTestCase {
func testInit() {
var array = [8, 6,5, 4,3,2,1]
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsGreaterThanOrEqualChildren)?.elements, array)
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsLessThanOrEqualChildren)?.elements, nil)
Heap(fromRepresenting: array, priority: .parentsLessThanOrEqualChildren)?.firstIndex(of: 5)
array = [1, 2,1, 2,1,2,1]
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsGreaterThanOrEqualChildren)?.elements, nil)
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsLessThanOrEqualChildren)?.elements, nil)
array = [1, 2,3, 4,5,6,7, 8,9,10]
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsLessThanOrEqualChildren)?.elements, array)
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsGreaterThanOrEqualChildren)?.elements, nil)
array = [1]
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsGreaterThanOrEqualChildren)?.elements, array)
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsLessThanOrEqualChildren)?.elements, array)
array = []
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsGreaterThanOrEqualChildren)?.elements, array)
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsLessThanOrEqualChildren)?.elements, array)
array = [1,1,1]
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsGreaterThanOrEqualChildren)?.elements, array)
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsLessThanOrEqualChildren)?.elements, array)
array = [1,2]
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsLessThanOrEqualChildren)?.elements, array)
XCTAssertEqual(Heap(fromRepresenting: array, priority: .parentsGreaterThanOrEqualChildren)?.elements, nil)
}
}
class HeapTests1: XCTestCase {
typealias Element = Int
typealias Collection = [Element]
func createDataForTest() -> Collection { [8, 6,5, 4,3,2,1] }
func createHeapsForTest() -> [Heap<Element>] {
let data = createDataForTest()
return [.init(insertElementsFrom: data, priority: .parentsLessThanOrEqualChildren),
.init(insertElementsFrom: data, priority: .parentsGreaterThanOrEqualChildren)]
}
func testInit() {
var dataForTest = createDataForTest()
var sortedDataForTest = dataForTest.sorted()
_testInit(dataForTest: &dataForTest,
sortedDataForTest: &sortedDataForTest,
priority: .parentsGreaterThanOrEqualChildren, sort: >=)
_testInit(dataForTest: &dataForTest,
sortedDataForTest: &sortedDataForTest,
priority: .parentsLessThanOrEqualChildren, sort: <=)
}
func testRemove() { for heap in createHeapsForTest() { assertValid(heap: heap) } }
func testRemoveAtIndex() {
var heaps = createHeapsForTest()
var tempArray: Collection
var indexToRemove: Int!
for index in 0..<heaps.count {
while !heaps[index].isEmpty {
tempArray = heaps[index].elements
indexToRemove = (0..<tempArray.count).randomElement() ?? 0
XCTAssertEqual(tempArray.remove(at: indexToRemove), heaps[index].remove(at: indexToRemove))
XCTAssertEqual(tempArray.count, heaps[index].count)
assertValid(heap: heaps[index])
}
XCTAssertTrue(heaps[index].isEmpty)
}
}
func testSort() {
for heap in createHeapsForTest() {
switch heap.priority {
case .parentsGreaterThanOrEqualChildren:
XCTAssertEqual(heap.elements.sorted(by: <=), heap.representAsReversedSortedArray())
case .parentsLessThanOrEqualChildren:
XCTAssertEqual(heap.elements.sorted(by: >=), heap.representAsReversedSortedArray())
}
}
}
func testInsert() {
let dataForTest = createDataForTest()
var sortedArray: Collection!
var sortedHeapElements: Collection!
var heaps = createHeapsForTest()
for i in 0..<heaps.count {
sortedArray = (heaps[i].elements + dataForTest).sorted()
dataForTest.forEach { heaps[i].insert($0) }
sortedHeapElements = heaps[i].elements.sorted()
XCTAssertEqual(sortedHeapElements, sortedArray)
XCTAssertEqual(heaps[i].count, sortedArray.count)
XCTAssertEqual(heaps[i].isEmpty, sortedArray.isEmpty)
assertValid(heap: heaps[i])
switch heaps[i].priority {
case .parentsGreaterThanOrEqualChildren: XCTAssertEqual(heaps[i].peek(), sortedHeapElements.max())
case .parentsLessThanOrEqualChildren: XCTAssertEqual(heaps[i].peek(), sortedHeapElements.min())
}
}
}
func testSearchAt() {
var heapElements: Collection!
var sortedHeapElements: Collection!
for heap in createHeapsForTest() {
heapElements = heap.elements
sortedHeapElements = heapElements.sorted()
for element in sortedHeapElements {
XCTAssertEqual(heap.firstIndex(of: element), heapElements.firstIndex(of: element))
}
}
}
private func _testInit(dataForTest: inout Collection,
sortedDataForTest: inout Collection,
priority: Heap<Element>.Priority,
sort: ((Element, Element) -> Bool)?) {
var heap = Heap(insertElementsFrom: dataForTest, priority: priority)
XCTAssertEqual(heap.elements.sorted(), sortedDataForTest)
assertValid(heap: heap, sort: sort)
heap = Heap(priority: priority)
dataForTest.forEach { heap.insert($0) }
XCTAssertEqual(heap.elements.sorted(), sortedDataForTest)
assertValid(heap: heap, sort: sort)
}
private func assertValid<Element>(heap: Heap<Element>, sort: ((Element, Element) -> Bool)? = nil) {
var heap = heap
var currentElement: Element?
var previousElement = heap.removeElementWithHighestPriority()
var elementWithMaxPriority: Element!
while !heap.isEmpty {
XCTAssertEqual(heap.isEmpty, false)
XCTAssertGreaterThanOrEqual(heap.count, 1)
switch heap.priority {
case .parentsGreaterThanOrEqualChildren: elementWithMaxPriority = heap.elements.max()
case .parentsLessThanOrEqualChildren: elementWithMaxPriority = heap.elements.min()
}
currentElement = heap.removeElementWithHighestPriority()
XCTAssertEqual(elementWithMaxPriority, currentElement)
if let sort = sort {
XCTAssertTrue(sort(previousElement!, currentElement!))
} else {
switch heap.priority {
case .parentsGreaterThanOrEqualChildren: XCTAssertGreaterThanOrEqual(previousElement!, currentElement!)
case .parentsLessThanOrEqualChildren: XCTAssertLessThanOrEqual(previousElement!, currentElement!)
}
}
previousElement = currentElement
}
XCTAssertEqual(heap.isEmpty, true)
}
}
class HeapTests2: HeapTests1 {
override func createDataForTest() -> Collection { [1, 2,1, 2,1,2,1] }
}
class HeapTests3: HeapTests1 {
override func createDataForTest() -> Collection { [1,2] }
override func createHeapsForTest() -> [Heap<Element>] {
let data = createDataForTest()
return super.createHeapsForTest() + [Heap(fromRepresenting: data, priority: .parentsLessThanOrEqualChildren)!]
}
}
class HeapTests4: HeapTests3 {
override func createDataForTest() -> Collection { [] }
override func createHeapsForTest() -> [Heap<Element>] {
let data = createDataForTest()
return super.createHeapsForTest() + [Heap(fromRepresenting: data, priority: .parentsGreaterThanOrEqualChildren)!]
}
}
class HeapTests5: HeapTests3 {
override func createDataForTest() -> Collection { [1] }
}
class HeapTests6: HeapTests3 {
override func createDataForTest() -> Collection { [1,1,1] }
}
class HeapTests7: HeapTests1 {
override func createDataForTest() -> Collection { [1, 20,3, 11,1,44,5, 7,33,45,21,44,41,31,0] }
}
一些想法来自Swift算法俱乐部。