바이너리 힙의 키 기능

Question

클래스를 사용하여 텍스트 북에이 바이너리 힙 구현 코드가 있습니다. 그러나 나는 힙을 만들 때 열쇠의 필요성을 이해하지 못합니다.

#define MAXREAL 999999.0 

class HeapItem 
{ 
    public: 
    int data; //actual data that is stored 
    float key; //key value of the data, heap is constructed based on key 
}; 
class MinHeap 
{ 
    public: 
    HeapItem * A; //stores heap items, e.g., nodes 
    int heapLength; 
    int * map; 

    MinHeap() //constructor 
    { 
     A = new HeapItem[MAX_HEAP_SIZE]; 
     map = new int[MAX_HEAP_SIZE]; 
     heapLength = 0; 
    } 
//Fills the heap with an array of integers 
//key values do not maintain heap property 
//May be used in some algorithms such as dijkstra's shortest path 
    void initialize(int v[], int n) 
    { 
     heapLength = n; 
     for (int i = 0; i<n; i++) //nodes are stored from index 1 instead of 0 in the heap 
     { 
      A[i + 1].data = v[i]; 
      A[i + 1].key = MAXREAL; 
      map[v[i]] = i + 1; //map tracks which vertex is stored at which heap node 
     } 
    } 
} 

MinHeap에서 키와지도의 기능은 무엇입니까? 키가 아무것도하지 않는 사용자의 경우

Answer 1

잘못 중 하나입니다, 힙 트리 key 값을 기준으로 구축 될 것이다. 예를 들어

: 빨간색 상자 안에 현재 가치는 key의 값에 구축되고 그래서는 분 힙이며, 이후 cirle 내부 key 및 값 data 이다. 루트의 key은 자식보다 작습니다.

Answer 2

, 그것은 심지어 의견 제시 :

//key values do not maintain heap property 
//May be used in some algorithms such as dijkstra's shortest path 

또한 모든 키가 keep the heap property하기 위해 사용할 수있는 MAXREAL 기본적으로 키에 할당되어 있습니다.

이 경우 힙이라고 부를 수 없습니다. Heapify 프로세스가 호출되지 않고 배열의 순서에 대한 가정이 없기 때문입니다. 기본적으로 데이터 집합에 특별한 순서가 없으므로 최소 힙이 아닙니다.

또한 힙 요소는 최소 위치 0에서 저장됩니다. 그것은 코드처럼 보이는

가 불완전하거나 여기