연결된 구조 힙의 마지막 요소 찾기

Question

힙과 루트 요소의 연결된 구조 구현에서 가장 먼 요소를 찾는 방법에 대해 궁금합니다. Enque와 Deque 요소를 원합니다.

일부 설명 : 내가 말한 것은 최대 힙 (루트 요소가 가장 큰 값을 가짐)을 구성하는 링크 된 구조가 있다고 가정합니다. 당신의 나무는 맨 아래에 어딘가에 엘리먼트를 가지고 있습니다. 엘리먼트는 당신이 enqueing 또는 dequeing하는 경우에 따라 삽입하거나 제거 할 것입니다. 그 요소를 어떻게 결정합니까? 트리의 루트 노드를 어떻게 결정합니까? (꼭대기) 나는이 완전히 긍정적 아니에요

Answer 1

은 당신이 요구하는 것입니다, 그러나 이것은 싱글 링크드리스트의 마지막 요소를 가리키는 방법 중 하나입니다 :

T *p = NULL, *q = NULL; // q follows p by one node 
p = root; 
while (p) 
{ 
    q = p; 
    p = p -> next; 
} 

// q now points to last node 

Answer 2

어쩌면 뭔가 이거?

struct node { 
    node *parent; 
    node *children[2]; 
    int data; //or whatever else you want 
}; 

struct heap { 
    node *root; 
    node *last; 
}; 

이것은 배열을 사용하여 구현하는 것이 훨씬 까다 롭습니다. 가상의 추가 내용은 다음과 같습니다.

void add(struct heap* h, int d) 
{ 
    node* add = malloc(sizeof(node)); 
    add->data = d; 
    node* current = h->root; 
    while(current->children[1]) current = current->children[1]; 
    current->children[1] = add; 
    add.parent = current; 
    add.children[0] = NULL; 
    add.children[1] = NULL; 
    h.last = add; 
    percolate_up(h); 
} 

그런 것 같습니다.

Answer 3

힙 구조에 무언가를 추가하는 일반적인 방법은 루트에서 시작하여 트리를 이동하여 새 요소가있는 위치를 찾습니다. 그것이 어디로 가는지를 발견하면, 그 위치에 놓습니다. 그리고 그것이 이미 그 자리에있는 것을 대체한다면, 이전 값을 취하고 계속해서 그것이 어디로 가는지 찾아야합니다. 잎을 칠 때까지 반복 한 다음, 그 잎의 적절한 자식으로 "들고 다니는"모든 값을 추가하십시오.

새 값이 5이고 힙의 루트 노드가 10이라고 가정합니다. 10이 분명히 10이되어 10의 자식을 봅니다. 이들이 8과 7이라고 가정합니다. 둘 다 5보다 크고, 그러니 하나 선택하십시오 (하나를 선택하는 방법은 힙을 균형있게 유지하려고하는지 여부에 달려 있습니다). 7을 고르고 그것이 3과 4의 자식을 가지고 있다고합시다. 5는 7보다 아래이지만 3이나 4보다 높기 때문에, 예를 들어 4를 5로 바꾸고, 그 노드의 자식을 보면서 4를 넣을 곳을 봅니다. 당신이 루트를 찾는 방법에 대한 질문에 관해서는 - 일반적으로 루트는 당신이 가지고있는 트리에 대한 유일한 포인터입니다. 모든 작업의 ​​출발점입니다. 다른 곳에서 시작했다면 루트까지 이동할 수 있다고 생각하지만 이유는 묻습니다.