우선 순위 대기열 힙 : 고정 bubbleDown 메소드

Question

우선 순위 대기열 (힙)에서 작업 중이며 기본 근거가 있다고 생각합니다. 내 방법은 모두 대부분의 부분에 의미가 있지만 내 bubbleDown 및 deleteMin 방법에 정말 고심한다고 생각합니다.

public class Heap { 
    private int n; 
    private Node[] s; 

    public Heap() { 
     s = new Node[128]; 
     n =0; 
    } 

    public boolean isEmptySet() { 
     return (n == 0); 
    } 

    public Node findMin() { 
     return s[0]; 
    } 

    public void insert(Node p) { 
     s[n] = p; 
     n = n+1; 
     bubbleUp(n - 1); // needs to subtract 1 because we do the addition 
     } 

    public void bubbleUp(int index) { 
     if (index == 0) { 
      return index; 
     } 

     else if (index > 0) { 
      int parentIndex = (index - 1)/2; // Might not need to subtract 1 
      if (s[index].getKey() < s[parentIndex].getKey()) { 
       swapNode(index, parentIndex); 
       bubbleUp(parentIndex); 
      } 
     } 
    } 

    public void swapNode(int index, int parentIndex) { 
     Node temp = s[index]; 
     s[index] = s[parentIndex]; 
     s[parentIndex] = temp; 
    } 

    public void deleteMin(Node p) { 
     n = n - 1; 
     bubbleDown(s[0], s[n]); 
     return s[n]; 
    } 


    public void bubbleDown(int index) { 
     if (index < 0) { 
      int leftChildIndex = (i*2) + 1; 
      int rightChildIndex = (i*2) + 2; 
      if (s[index].getKey() > s[leftChildIndex].getKey()) { 
       swapNode(index, leftChildIndex); 
       bubbleDown(leftChildIndex); 
      } else if (s[index].getKey() < s[leftChildIndex].getKey() && s[index].getKey() > s[rightChildIndex].getKey()) { 
       swapNode(index, rightChildIndex); 
       bubbleDown(rightChildIndex); 
      } 
     } 
    } 
} 

Answer 1

먼저 bubbleUp()에서 1을 빼서 부모를 찾아야합니다. 0의 자식이 1과 2 인 것을 고려하십시오. 나누기 전에 1을 뺀 것이 아니라면 2의 부모는 1로 잘못 계산됩니다.

findMin()에서 전에 비어있는 힙이 있는지 확인해야합니다 맹목적으로 루트 항목을 반환합니다. isEmptySet() 함수가 있지만, 빈 힙으로 호출하면 findMin() 예외가 발생합니다.

이제 deleteMin() 및 bubbleDown(). deleteMin은 다음과 같아야합니다

public void deleteMin(Node p){ 
    n = n - 1; 
    // place root node at the end of the heap, 
    // and the last node at the root. 
    swapNode(0, n); 

    // adjust the heap 
    bubbleDown(0); 
    return s[n]; 
} 

방법은 deleteMin이 bubbleDown에 노드 인덱스가 아닌 노드를 통과되었고, bubbleDown 하나만을 허용 할 때 두 개의 매개 변수를 전달하고, 그것을했다.

귀하의 bubbleDown은 올바른 경로에 있지만 조심해야합니다. 버블 링 규칙은 노드가 자식 노드보다 큰 경우 두 노드 중 가장 작은 노드로 노드를 교체한다는 것입니다. 그리고 노드에 자식이 전혀 없을 수도 있으므로 잠재적 인 두 자식을 모두 맹목적으로 확인할 수 없습니다. 따라서 :

public void bubbleDown(int index){ 
    int childIndex = (index * 2) + 1; 
    if (childIndex > n) 
    { 
     // if the first child index is off the end of the heap 
     // then the item has no children. (It's a leaf.) 
     return; 
    } 

    // first find the smallest child 
    // This test is to prevent checking a right child that doesn't exist. 
    if (childIndex < n) 
    { 
     if (s[childIndex] > s[childIndex+1]) 
     { 
      childIndex = childIndex + 1; 
     } 
    } 

    // childIndex holds the index of the smallest of the node's children. 
    // swap if the parent is larger than the smallest child, 
    // and then keep bubbling down. 
    if (s[index] > s[childIndex]) 
    { 
     swapNode(index, childIndex); 
     bubbleDown(childIndex); 
    } 
}