이전 글의 모음 01 부분부터 모음에서 항목을 삽입하고 삭제할 때 발생하는 모음 정렬을 설명합니다.내가 지난번에 말한 내용을 되돌아보게 해 주세요.parent (), left\u child (), right\u child () 와 같은 최소 무더기 예시와 기본 방법을 만들고 있습니다.

학습 알고리즘 - 쌓기 | 섹션 01

양(Jenny Yang)・ 10월 18일・ 4분 읽기

#computerscience #algorithms #heap #datastructures

어기다

무더기의 충돌은 하위 노드가 가장 큰 무더기의 아버지 노드보다 크거나 하위 노드가 가장 작은 무더기의 아버지 노드보다 작다는 것을 가리킨다.

삽입

우리는 무더기 정렬을 이해하기 위해 항목을 삽입하는 방법에 대한 간단한 예시를 볼 것이다.우선, 우리는 순서에 7, 1, 3을 삽입할 것이다.

insert(7)
insert(3)
insert(1)

눈치챘어?우리가 한 항목을 삽입할 때마다 두 항목을 비교한다. 하나는 아버지이고 다른 하나는 자식이다. 충돌이 발생하면 이 두 항목을 교환한다.주어진 예시의 항목을 계속 삽입합니다.

insert(20)
insert(11)
insert(9)

지금까지 우리는 7, 3, 1, 20, 11과 9를 삽입했다.2라운드는 아무런 교환도 없었다.다음 라운드에 들어가다.

insert(3)
insert(15)
insert(4)
insert(13)

우리는 20과 15를 교환했다. 15는 아버지 노드 20보다 작고 아버지 노드 7로 이동하며 아버지 노드 7은 아버지 노드 15보다 작기 때문에 모두 정렬되었다.

처음 [9]에 삽입된 숫자 4는 상위 항목과 교환될 때마다 [2]로 이동합니다.마지막 라운드는 13을 삽입하여 끝까지 버티는 것이다.

최종 결과

최소 값 추출

Extract min은 더미에서 삭제하는 방법입니다.전반적으로 말하면 두 가지 절차가 있다.

삭제: 교환[1]과 [n], 그중 n=더미의 길이는 [0]를 배제하고 최소 항목으로 [n]을 삭제한다.

무더기 정렬: [1]의 항목이 하위 항목보다 작을 때까지 교환합니다.

1단계: 삭제

단계 2: 쌓기 정렬

교환

Swap 방법은 두 항목만 교환할 뿐 heapify () 방법에서 사용됩니다.

def swap(self, a, b):
    self.heap[a], self.heap[b] = self.heap[b], self.heap[a]

히피피

무더기 속성에 충돌이 존재할 때마다 우리는 하위 등급과 부모 등급을 교환함으로써 충돌을 바로잡을 것이다.내가 말한 규칙 위반은 자식 대상이 가장 작은 무더기에서 아버지 대상보다 작을 때를 가리킨다.귀속 또는 교체를 사용하는 데는 두 가지 실현 방법이 있다.삽입과 삭제는 항상 실행이 끝날 때heapify를 실행하여 무더기의 정렬을 유지합니다.

교체하다

def heapify(self, i):
    parent = i // 2
    """ 
    as long as the element is in the range of index of a heap 
    (0 is not included)
    """
    while i // 2 > 0:
        # if the element is bigger than its parent swap them
        if self.heap[i] < self.heap[parent]:
            self.swap(parent, i)

        # move the index to the parent
        i = i // 2

코드를 한 줄씩 분해해 보겠습니다.

while i // 2 범위 내에서만 (1에서 n)

self.heap[i] < self.heap[parent] 현재 노드가 부모 노드보다 작으면 부모 노드가 작아야 하기 때문에 이 두 노드를 교환합니다.

i = i // 2는 모회사에 거품이 되어 규칙 위반 행위를 계속 검사하는 것을 의미한다.

주: i 이 책에서 페이는 자아이다.마지막 색인 크기

차례로 돌아가다

def heapify(self, i):
    l = self.left(i)
    r = self.right(i)
    smallest = i

    """
    if the r and l are within the range of index,
        and if one of those are smaller than i,
        swap them with i
    """
    if l <= self.size and self.heap[l] < self.heap[i]:
        smallest = l
        print(f"now smallest is {self.heap[l]}")
        self.swap(i, smallest)
    if r <= self.size and self.heap[r] < self.heap[i]:
        smallest = r
        self.swap(i, smallest)

    """
    recursively do the process(heapify) above
    until i becomes smallest in the three relationships in the tree
    """
    if smallest != i:
        self.heapify(i)

장애 발생:
i= 부모 노드
세 개의 바늘이 왼쪽 자항, 오른쪽 자항, 그리고 가장 작은 자항을 가리킨다.여기서 중요한 것은 이곳i ≤ l or r을 기억하는 것이다.
만약 l 또는 r 색인 범위 내에 있고 그 중 하나가 i 보다 작으면 i 과 교환합니다. 왜냐하면 i 가 가장 작아야 하기 때문입니다.

이 과정을 반복적으로 실행하여 i 세 개(좌자, 우자, 부 i) 중에서 가장 작아질 때까지 한다.

실시

이 두 개의 삽입은 기본적으로 같고,heapify 방법이 수신하는 매개 변수는heapify 방법이 다르기 때문에 다르다.먼저 새 노드를 추가한 다음 크기를 늘립니다.마지막으로 더미를 정렬합니다.

삽입:교체

def insert(self, key):
    self.heap.append(key)
    self.size += 1
    # Fix violation if there is one
    # iteration heapify
    self.heapify(self.size)

반복 삽입에서 heapify는 마지막 인덱스를 찾습니다.

삽입:반복

def insert(self, key):
    self.heap.append(key)
    self.size += 1
    # Fix violation if there is one
    # recursion heapify
    self.heapify(self.size // 2)

귀속 삽입에서, heapify는 마지막 항목의 부모 인덱스를 사용합니다.
삽입 시간 복잡도는 추가 O (1) + 크기 변경 O (1) + heapify O (log n) = O (log n)

삭제(최소값 추출)

코드 분해:

삭제할 항목 저장

루트와 마지막 교환

최소 항목

이 있는 마지막 항목 삭제

기준을 충족할 때까지 정렬

뜯은 물품 반환

def extract_min(self):
    popped = self.heap[1]
    # swap last item and the root(min) item
    self.swap(self.size, 1)
    # pop the last item off
    self.heap.pop()
    # reduce size of the heap as an item is deleted
    self.size -= 1
    # sort the heap
    self.heapify(1)
    # return the popped item
    return popped

좀 늦추시겠어요?
삭제 시간 복잡도는 교환 O(1) + 삭제 O(1) + 크기 변경 O(1) + heapify O(log n) = O(log n)

시간 분석

Heapify는 이 알고리즘에서 중요한 역할을 합니다.삽입과 삭제의 다른 단계는 정해진 시간이기 때문에 우리가 진정으로 관심을 가지는 것은heapify 방법이다.왜 heapify가 대수 시간이 필요한지 설명해 드릴게요.

만약N = 9, 최악의 경우heapify는 최대 4단계가 필요하기 때문에 나무의 높이는 heapify 함수를 처리하는 시간이 됩니다.N을 대수 공식으로 바꿉니다.

2 ³는 대체로 9이므로 heapify는 O(log N)
나는 또 하나의 고급 방법을 설명해야 한다.세 번째 부분에서 봐요!