이 문장에서 나는 가장 간단한 나무 중의 하나인 Heap에 대해 이야기하고 싶다.시작합시다!

우선 순위 대기열

더미를 이해하기 전에 우선순위 대기열이 무엇인지 알아야 합니다.우선순위 대기열은 추상적인 데이터 형식(ADT)으로 그 중에서 데이터는 우선순위가 있고 우선순위가 높은 데이터는 먼저 삭제된다.그것은 세 가지 주요 조작이 있다.잠깐만, 추상적인 데이터 형식은 무엇입니까?이것은 대기열과 창고와 유사한 데이터 구조이다.

삽입 (Q, x) - 키가 x인 항목을 우선 순위 대기열 Q에 삽입하기

최대(Q) 또는 최소(Q) - 우선 순위 대기열 Q

의 다른 키보다 큰 키 또는 최소 키로 돌아가기

최대값 추출(Q) 또는 최소값 추출(Q) - 우선 순위 대기열 Q

에서 max 또는min 항목 삭제

더미 및 우선 순위 대기열

그러면 무더기와 우선순위 대기열 간의 관계는 무엇입니까?우선순위 대기열은 수조, 체인 테이블과 더미로 실현할 수 있으며 더미는 그 중에서 가장 효과적인 실현이다.

무더기가 뭐예요?

쌓는 유형

가장 큰 무더기와 가장 작은 무더기는 두 가지 유형이 있다.모든 유형은 순서를 유지하기 위해 서로 다른 기준이 있다.가장 많은 무더기에서 부모 노드의 키 값은 항상 하위 노드보다 크고 반대로도 마찬가지다.
더미는 일정한 시간 (O (1) 에서 최대치나 최소치를 찾을 수 있도록 우선순위 대기열을 실현하는 두 갈래 트리 (근사함) 이다.더미는 부모 노드와 하위 노드로 구성되어 있다.그 하위 항목은 크거나 같아서는 안 된다 (child)≤ 모 피쳐) 또는 보다 작거나 같음(자 피쳐)≥ 부모 노드).그 밖에 같은 데이터를 허용합니다. 우리는 이 데이터를 키라고 합니다.
더미는 사실상 하나의 수조로 완전한 두 갈래 나무로 가시화될 수 있다.수조 AA=[20, 15, 13, 11, 7, 9, 3, 3, 4, 1]가 있는데 다음과 같이 가시화할 수 있다.

규칙:쌓는 순서

쌓인 충전 순서는 위에서 아래로, 왼쪽에서 오른쪽으로 해야 한다.따라서 상응하는 인덱스는 루트 1에서 n으로 시작됩니다. 이런 시각화를 통해 더욱 쉽습니다.

우리의 수조의 크기는 11로 최대 무더기를 나타낸다.실현하기 편리하도록 인덱스 1부터 시작하기 때문에 인덱스 0을 사용하지 않습니다.

이것은 한 무더기입니까?

아래의 예를 보고 이것이 무더기인지 아닌지를 추측해 봅시다.이 나무는 한 무더기입니까?

아니오, 이것은 한 무더기가 아닙니다.왜?루트 원소의 키는 최대치도 최소치도 아니며 각 노드도 순서 규칙을 따르지 않기 때문에 무더기의 정의에 위배된다.
밑에 이 나무 어때요?이것은 한 무더기입니까?

네, 이것은 가장 큰 무더기입니다. 그 중에서 뿌리의 키가 가장 큰 값을 가지고 있습니다.
그림이 쌓인 밑에 있습니까?

알아맞혀 봐, 아니야!모든 요소는 왼쪽에서 채워지지 않기 때문이다.요소에 키 1이 있기 때문에 충돌이 있습니다.

무더기의 실현

이제 우리는 쌓인 것이 무엇인지 알게 되었다.실시할 때가 되었다.생성된 그룹을 만드는 클래스부터 시작합니다.인덱스 0 를 사용하지 않습니다. 인덱스 순서를 더욱 간단하게 합니다.

 def __init__(self):
     self.heap = [0]
     self.size = len(self.heap) - 1

쌓는 방법

쌓는 기본적인 방법은 다음과 같다.

부모님(i)

좌_자(i)

right_child(i)

삽입(키)

최소값 ()/최대값 ()

extract\umin()/extract\u max()(delete 방법)

heapify(i)

학부모 (1)

parent of i = i / 2 정수 제법을 사용하여 i가 노드의 인덱스라고 가정하면 부모 인덱스는 i/2이다.예를 들어, i=3, (인덱스) 의 경우 상위 항목은 3/2=1입니다.

색인 수는 소수가 아니라 정수이기 때문에 우리는 부모 항목을 얻기 위해 정수 나누기를 할 것이다.soparent(3) = 1.

왼쪽 _자 (i)

이것은 i의 왼쪽 하위 인덱스 left child = 2 * i 를 되돌려줍니다.예: i = 3, i * 2 = 6

오른쪽 _자 (i)

이것은 i의 오른쪽 자대 인덱스,'오른쪽 자대 = 2*i+1For example, 'i =1, 2 * i + 1 = 3

def parent(self, i):
    return i // 2

def left(self, i):
    return 2 * i

def right(self, i):
    return (2 * i) + 1 

최소 ()

최소 무더기의 최소 노드는 항상 루트 노드이기 때문에 색인에 있는 루트 1 를 되돌려줍니다.

def min(self):
    return self.heap[1]

자, 얘들아, 나 피곤해... 계속 2부에서 힙을 소개할 거야.그때 봐요.