힙 - 최소 및 최대

힙 - 최소 힙

힙은 우선순위 목록보다 더 효율적인 버전입니다. 정렬되지 않은 삽입 비용은 O(1), 제거 비용은 O(n)인 반면, 정렬된 삽입 비용은 O(n)이고 제거 비용은 O(1)입니다.

	sorted	unsorted
insert	O(n)	O(1)
remove	O(1)	O(n)

힙은 배열로 구성되지만 그 표현은 이진 트리입니다. 우선순위가 가장 높은 요소는 맨 위, 즉 루트에 있습니다. 위에서 아래로, 오른쪽에서 왼쪽으로 아이들이 하나도 빠지지 않고 채워져 있어요!

?

그러나 가장 높은 키 값에 의해 정의되는 가장 높은 우선순위의 데이터 구조를 구축할 가능성이 있습니다. 이 경우에는 나중에 보게 될 최대 힙이 있습니다.

최소 힙

유효한 힙이 되려면 모든 하위 요소의 우선순위가 상위 요소보다 낮거나 같아야 합니다. 또한 누락된 하위 항목 없이 완전해야 합니다. 그렇지 않으면 배열에 공백이 생깁니다.

?

이 정의를 수행하는 보다 공식적인 방법은 이진 트리의 레벨 0, 1, 2, · · · h − 1에 가능한 최대 요소가 있고 레벨 h에 존재하는 요소가 할당되면 이진 트리가 완성된다고 말하는 것입니다. 최대한 왼쪽으로.

앞서 언급한 대로 힙은 배열(녹색으로 표시)로 구성되어 있지만 아래 이미지와 같이 트리 구조로 볼 수도 있습니다.

힙을 어셈블하는 방법에는 첫 번째 요소가 위치 0에 있거나 위치 0이 없는 두 가지 방법이 있습니다. 이 기사에서는 두 경우의 차이점을 살펴보겠습니다. 맨 위에 있는 요소에는 항상 하위 요소를 발견하기 위한 하위 요소가 있습니다. 인덱스 0의 경우 다음 계산을 사용하여 이 정보를 얻을 수 있습니다.

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

0이 채워지지 않은 버전을 사용하는 경우 합계를 줄이면 됩니다. 즉, 1-1=0, 상위 사례에서는 인덱스 / 2입니다.

끼워 넣다

항상 마지막에 추가됩니다. 유일한 관심은 하위 요소가 상위 요소보다 낮은 키를 가지고 있는지 확인할 때입니다. 이 목적을 위해 삽입된 요소의 키가 다음과 같을 때 버블링이 수행됩니다. 필요한 경우 아버지와 비교하여 변경합니다.

더 자세히 말하자면, 요소를 트리의 마지막 빈 공간에 배치하고 해당 키를 부모의 키와 비교해야 하므로 해당 키에 액세스하려면 부모의 인덱스를 계산해야 합니다. 아버지를 찾으려면 언급된 계산을 사용하십시오.

parent = (indexDoFilho -1)/2

이를 위해 indexDoFilho가 누락되었습니다. 이를 얻기 위해 변수를 현재 인덱스로 사용합니다. 마지막에 추가되는 삽입에 있는 것처럼 현재 인덱스는 마지막 인덱스입니다.

currentIndex = size-1

이제 현재 인덱스가 있으면 Parent를 호출하여 삽입되는 요소의 부모가 누구인지 알아보세요. 트리를 올바르게 구성하려면 이 요소를 상위 요소와 비교해야 하고 키가 더 작은 경우 위치를 바꿔야 하기 때문에 이 새 요소의 상위 요소가 필요합니다.

현재 인덱스가 0보다 크고(사용할 수 없는 인덱스 선택을 피하기 위해) 현재 인덱스가 상위 인덱스보다 작은 경우, 이 조건이 true이면 요소를 상위 인덱스와 교환해야 합니다. 최소 힙의 소유권을 보장하기 위해 스왑이 발생하고 현재 인덱스가 상위 인덱스를 받은 다음 상위 인덱스(KKKKK)를 가져옵니다. 스왑(Swap)은 정상적인 가치교환의 구조를 이용하는 방식입니다.

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

연관:

parent = (indexDoFilho -1)/2

스왑은 값을 교환하는 일반적인 방법입니다.

currentIndex = size-1

현재(하위) 요소의 값이 상위 요소의 값보다 작은 경우 이는 최소 힙 속성을 위반했음을 나타냅니다. 최소 힙에서 부모는 항상 자식보다 작거나 같아야 합니다. 이 조건이 충족되지 않으면 자식은 부모와 함께 위치를 변경해야 합니다 더 작은 값이 속성이 유지되는 올바른 위치를 찾을 때까지 힙에서 계속 "등반"합니다.

제거하다

인덱스 0 요소를 제거하지만 트리는 더 이상 완전하지 않습니다! 이 문제를 해결하려면 배열의 마지막 요소를 처음으로 끌어옵니다. 즉, 추가된 마지막 요소가 트리의 맨 위로 이동합니다. 그 후 다시 확인하되 이제 위에서 아래로 확인하십시오. 즉, 이제는 부모와 자녀를 비교할 때입니다! (싱크다운)
inkDown() 메서드는 요소가 올바른 위치에 올 때까지 힙에서 요소를 아래로 이동(또는 "싱크")합니다. 해당 위치의 값은 자식의 값보다 작거나 같습니다(자식이 있는 위치에 있는 경우). .
inkDown에는 루트에서 시작하는 가장 낮은 키를 가진 요소의 인덱스를 저장하는 변수와 현재 인덱스에 대한 또 다른 변수가 있습니다. 그런 다음 현재 요소의 인덱스가 가장 낮은 키를 가진 요소의 인덱스와 같아질 때까지 지속되는 루프입니다. 루프 내에서 현재 항목의 하위 항목을 가져와서 하위 항목이 배열 범위 내에 있는지 확인하고 하위 항목의 인덱스가 최소 인덱스보다 작으면 최소값을 업데이트합니다.

public void insert(K key, V value) { //o(log n)
    if (isFull()){
        throw new RuntimeException("full");
    }
    //adc a entry na ultima posição do vetor
    heap[size++]=new PriorityEntry(key, value);
    //guarda o index que esse novo elemento tá
    int currentIndex = size-1;
    //chama o método parent pra calcular quem é o pai do novo elemento
    int parent = parent(currentIndex);
    //percorre enquanto o index nao for o 0 e o index ser 
    while (currentIndex>0 && compare(currentIndex, parent)<0){
        swap(currentIndex, parent);
        currentIndex = parent;
        parent = parent(currentIndex);
    }
}

이 경우:

protected int parent(int index){
        return (index-1)/2;
}

요약:

최소 힙 속성:

• 완전한 이진 트리 구조.
• 상위 노드는 항상 하위 노드보다 작거나 같은 값을 갖습니다.
• 배열을 통해 구현되며, 여기서 하위 항목과 상위 항목의 위치는 인덱스 기반 수식으로 결정됩니다.

자녀와 부모의 위치를 ​​계산하려면:

• 왼쪽: leftChild = 인덱스 * 2 1
• 오른쪽: rightChild = 인덱스 * 2 2
• 부모: 부모 = (색인 - 1) / 2

인덱스 0이 없는 버전: 계산에서 1을 빼면 다음과 같습니다.

• leftChild = 인덱스 * 2
• rightChild = 인덱스 * 2 1
• 상위 = 인덱스 / 2

힙 - 최대 힙

가장 높은 값은 루트에 있으므로 상위 노드는 하위 노드와 같거나 더 큰 값을 갖습니다

자녀와 부모 계산 공식:

• 왼쪽: leftChild = 인덱스 * 2 1
• 오른쪽: rightChild = 인덱스 * 2 2
• 부모: 부모 = (색인 - 1) / 2

끼워 넣다

끝에 요소를 추가하고 요소를 상위 요소와 비교하여 필요한 경우 위치를 변경합니다. O(log n).

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

제거하다

루트라고도 불리는 heapMax[0] 요소를 제거한 다음 마지막 요소를 가져와 루트로 이동하고,inkdown을 호출한 다음 올바른 위치를 찾을 때까지 새 요소를 루트에서 아래로 밀어냅니다.

sinkDown은 상위 노드의 값이 하위 노드의 값보다 크거나 같은지 확인해야 합니다. 따라서 노드를 싱크할 때 가장 큰 자식

과 비교됩니다.

최소 힙에서 싱크Down은 상위 노드의 값이 하위 노드의 값 이하인지 확인해야 합니다. 이 경우에는 가장 작은 아이를 기준으로 비교합니다.

parent = (indexDoFilho -1)/2

currentIndex = size-1

차이점

• 최대 힙에서 싱크Down은 상위 노드의 값이 하위 노드의 값 크거나 같은지 확인해야 합니다. 따라서 노드를 싱크할 때 가장 큰 자식
과 비교됩니다.
• 최대 힙에서 상위 노드가 하위 노드 중 가장 큰 노드보다 작은 경우 가장 큰 하위 노드로 교체하여 가장 큰 값이 최대한 높도록 해야 합니다.
• 최소 힙에서 싱크Down은 상위 노드의 값이 하위 노드의 값 이하인지 확인해야 합니다. 이 경우에는 가장 작은 아이를 기준으로 비교합니다.
• Min Heap에서는 상위 노드가 하위 노드 중 가장 작은 노드보다 크면 전환이 발생하고 가장 작은 값을 맨 위에 유지합니다

위 내용은 힙 - 최소 및 최대의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!