인덱스 우선 순위 큐의 혼란

Question

나는 우선 순위 큐에 대한 아이디어를 가지고있다.하지만 인덱스 우선 순위 큐에 관해서는, 나는 약간의 메소드 구현과 혼동된다. 변경 (int k, 항목 항목) 및 삭제 (int i).

변화 (INT의 K, 상품 아이템)

삭제 항목 (K)와 연관된 항목을 변경하는 K와 연관된 항목을 제거하는 것 (전 INT)

public void changeKey(int i, Key key) { 
     if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); 
     if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); 
     keys[i] = key; 
     swim(qp[i]); 
     sink(qp[i]); 
    } 

public void delete(int i) { 
     if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); 
     if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); 
     int index = qp[i]; 
     exch(index, n--); 
     swim(index); 
     sink(index); 
     keys[i] = null; 
     qp[i] = -1; 
    } 

private void swim(int k) { 
     while (k > 1 && greater(k/2, k)) { 
      exch(k, k/2); 
      k = k/2; 
     } 
    } 

    private void sink(int k) { 
     while (2*k <= n) { 
      int j = 2*k; 
      if (j < n && greater(j, j+1)) j++; 
      if (!greater(k, j)) break; 
      exch(k, j); 
      k = j; 
     } 
    } 


private int maxN;  // maximum number of elements on PQ 
private int n;   // number of elements on PQ 
private int[] pq;  // binary heap using 1-based indexing 
private int[] qp;  // inverse of pq - qp[pq[i]] = pq[qp[i]] = i 
private Key[] keys;  // keys[i] = priority of i 

싱크 및 수영의 작동을 이해합니다. 그러나 이유는 입니다. (int i) 및 eKey (int i, Key key)에는 swim(qp[i]/index);과 sink(qp[i]/index);의 문장이 있습니다.

우선 순위 큐와 인덱스 우선 순위 큐 사이의 요소 구성 스타일을 알고 인덱스 우선 순위 큐의 이진 힙에 저장되는 내용은 무엇입니까?

Answer 1

키를 변경할 때 수행해야하는 힙에 대한 작업입니다. 우선 순위 큐에있는 모든 '노드'는 힙에 보관됩니다. 항목을 추가 할 때 해당 항목을 올바른 위치에 배치해야하므로 '힙 규칙'이 손상되지 않습니다. 키를 변경하는 경우에도 마찬가지입니다. 힙에서 항목의 위치를 ​​변경하여 규칙이 손상되지 않도록해야합니다 (해당 항목의 하위 항목은 하위 항목보다 크지 않으며 해당 항목의 상위 항목은 작지 않습니다). 이 우선 순위 큐는 바이너리 힙으로 구현됩니다. 즉, 바이너리 트리를 기반으로하므로 해당 방법에서 2로 나누는 것을 볼 수 있습니다. 왜냐하면 항목을 위/아래로 레벨별로 가져와야하기 때문입니다. 첫 번째 수준에는 한 노드가 있고 두 번째 수준에는 두 개의 노드가 있고 세 번째 수준에는 네 개의 노드가 있습니다. 노드 수에는 각 수준이 2로 곱 해짐). 이 게시물은 거대하고 폭 넓은 주제에 대한 소개 일 뿐이며, 특히 ('heapify'섹션과 관련하여) 자세한 내용을 읽어 보시기 바랍니다. 특히 check this out.

일반적으로 키를 변경하는 방법은 1 개 뿐이며 swim 이전 키가 더 높거나 낮을 수 있으므로 sink입니다. 대개 decreaseKey과 increaseKey의 두 가지 방법으로 수행되며 각 메서드는 sink 또는 swim 중 하나만 호출합니다. 귀하의 코드는 2 가지 방법이 1로 결합되어 있기 때문에 sink과 swim을 모두 호출합니다. 새 키가 이전 키보다 높으면 힙 (swim)에 올라야하고 새 키가 이전 키보다 작을 때 내려야합니다 (sink).

btw. 내 모든 게시물은 우리가 최대 힙을 가지고 작업하고 있다고 가정하고있다. 즉, 루트 노드가 최대 값을 갖고 그의 자식들이 더 작은 값을 갖는다는 것을 의미한다. 또한 정확한 쇠퇴 인 최소 힙이있다.