힙 데이터 구조 구현 신속한

Question

힙 데이터 구조에 대한 질문이 있습니다.

나는 세 가지 공용 기능을 가지고 있습니다. 올바른 기능을 수행 할 수 없습니다. 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) {} 
} 

Answer 1

4.

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") 
} 
} 
}