당신의 데이터 더미 구조의 완전한 지침!

안녕하세요, 저는 아야바우키하입니다. 이 아름다운 날에 저는 데이터 구조를 설명할 것입니다.
#22일차

더미의 정의

Heap: 완전한 두 갈래 나무 () (노드마다 최대 두 개의 자 노드가 있고 모든 잎은 왼쪽으로 기울어야 한다) 로 뿌리 노드와 자 노드를 비교하고 그에 상응하여 배열한다.

전체 두 갈래 트리 예

불완전한 두 갈래 나무 예

더미의 유형

1. 최대 더미

모든 노드의 키는 부모 노드보다 작거나 같다arr[parent] >= arr[i]

가장 많은 예

2.최소더미

각 노드의 키가 상위 노드보다 크거나 같음arr[parent] <= arr[i]

최소 무더기의 예

무더기의 응용

더미 정렬 알고리즘

일정 시간 동안 최소치 또는 최대치의 순서 통계 정보를 얻기

Prim 알고리즘과 Dijkstra 알고리즘 등 도형 알고리즘

우선 순위 대기열

쌓인 공간과 시간의 복잡성

쌓인 공간의 복잡도는 O (n) 이다
삽입(밀어넣기)
삭제(pop)
훔쳐보다
O(대수 n)
O(대수 n)
O(1)

더미 진열 실현

max heap을 예로 들겠습니다.
각 노드의 인덱스는 괄호() 사이에 있습니다.

          15(0)
      /          \
 (1) 9            13 (2)
    /  \         /
(3)5  (4)7   (5)11

arr = [15, 9, 13, 5, 7, 11]

다음과 같은 방법으로 구현할 수 있습니다.

뿌리를 수조의 첫 번째 원소로 만들기arr[0] = root

상위 노드: arr[(i - 1) // 2]

왼손잡이: arr[2 * i + 1]

정확한 아이: arr[2 * i + 2]

class MinHeap:
    def __init__(self):
        self.heap = []
        self.heap_size = 0

    def getParentNodeIndex(self, i: int) -> int:
        return (i-1)//2

    def getLeftChildNodeIndex(self, i: int) -> int:
        return 2*i+1

    def getRightChildNodeIndex(self, i: int) -> int:
        return 2*i+2

    def hasParent(self, i: int) -> bool:
        # cheking if a node has a parent
        return self.getParentNodeIndex(i) < len(self.heap)

    def hasLeftChild(self, i: int) -> bool:
        # cheking if a node has a left child
        return self.getLeftChildNodeIndex(i) < len(self.heap)

    def hasRightChild(self, i: int) -> bool:
        # cheking if a node has a right child
        return self.getRightChildNodeIndex(i) < len(self.heap)

    def getMinValue(self) -> int:
        """
            time complexity => O(1)
        """
        return self.heap[0]

    def printAll(self):
        print(self.heap)

스택에 삽입(밀어넣기)

1. 삽입 방법

더미의 크기를 늘려 새로운 원소를 추가

더미는 완전한 두 갈래 나무이다. 이것이 바로 새로운 원소가 왼쪽으로 기울어야 하는 원인이다. 즉, 수조 표시에서 우리는 원소를 수조의 끝에 삽입한다.

Heap은 Heap order 속성을 충족시켜야 합니다. 이것이 바로 Heapify 또는 거품이 생겨야 하는 이유입니다. Heapify 또는 거품이 생겨야 하는 이유는 새 요소를 부모 요소와 교환하는 것입니다.

그 부급은 가장 많은 무더기에서 그것보다 크거나 같다.

그 부급은 최소 더미에서 작거나 같다.

1. 설명 삽입

더 잘 이해하기 위해서 우리는 예를 들자.
저희가 이 작은 더미에 1을 넣고 싶어요.

        3 (0)
      /   \
 (1) 5     10 (2)
   / 
  9 (3)  

  [3, 5, 10, 9]

그룹 끝에 새 요소 삽입

         3 (0)
       /   \
 (1)  5     10 (2)
    /  \ 
(3)9 (4)1 

  heap_size += 1
  arr = [3, 5, 10, 9, 1]

새로운 원소를 담그기

1이 5보다 작기 때문에

         3 (0)
       /   \
 (1)  1     10 (2)
    /  \ 
(3)9 (4)5 

  arr = [3, 5, 10, 9, 1]
  newElementIndex = len(arr) - 1 # 4
  # the index of the parent of the new element
  ParentIndex = (newElementIndex - 1) // 2 # (4-1)//2 = 1 
  # 1 < 5 
  if arr[newElementIdx] < arr[ParentIdx]:
      # swap(1, 5)
      arr[newElementIdx], arr[ParentIdx] = arr[ParentIdx], arr[newElementIdx]

스토리지는 다음과 같습니다.

arr = [3, 1, 10, 9, 5]

따라서 1<3, 그것들을 교환하기 때문에:

         1 (0)
       /   \
 (1)  3     10 (2)
    /  \ 
(3)9 (4)5 

우리는 1과 3에 대해 같은 과정을 수행할 것이다. 예를 들어 (1과 5)이기 때문에 수조는

arr = [1, 3, 10, 9, 5]

3.python에 삽입된 실현

python에서 bubble up 또는 Heapify 함수의 실현

    def bubbleUp(self, i: int):
        parentIndex = self.getParentNodeIndex(i)
        if parentIndex < 0:
            parentIndex = 0 
        # Loops until it reaches a leaf node
        while(i > 0 and self.heap[i] < self.heap[self.getParentNodeIndex(i)]): 
            # Swap the elements
            self.heap[i], self.heap[self.getParentNodeIndex(i)] = self.heap[self.getParentNodeIndex(i)], self.heap[i]
            i = self.getParentNodeIndex(i) 

python에 함수 삽입

    def insert(self, value: int):
        self.heap_size += 1
        # insert the element at the end
        self.heap.append(value) 
        # bubble up the new element
        self.bubbleUp(len(self.heap) - 1)

더미에서 삭제

1. 삭제 방법

쌓아 올리는 표준 삭제 작업은 루트를 삭제하는 것입니다. 이것은 max Heap의 최대 값이자 in Heap의 최소 값입니다.

원소를 삭제하기 위해 더미의 크기를 줄인다

루트를 마지막 요소

와 교환

팝업(삭제) 그룹의 마지막 요소

Heap은 Heap order 속성을 충족시켜야 한다. 이것이 바로 우리가 아래로 거품을 일으켜야 하는 이유이다. (heapify,percolate down,sift down,sink down,trickle down,heapify down,cascade down,extract min 또는extract max 또는down Heap이라고도 부른다) 새로운 요소가 아래로 거품을 일으켜 새 요소와 그 하위 요소 중 하나를 교환할 때까지

가장 많은 무더기 중에서 하위 등급은 그것보다 작거나 같다.

최소 더미에서 하위 등급은 그것보다 크거나 같다.

1. 설명 삭제

더 잘 이해하기 위해서 우리는 예를 들자.
저희가 이 작은 더미 중 3개를 삭제하고 싶어요.

        3 (0)
      /   \
 (1) 5     10 (2)
   / 
  9 (3)  

  [3, 5, 10, 9]

루트와 마지막 요소 교환

         9 (0)
       /   \
 (1)  5     10 (2)
    /  
(3)3 

  arr = [9, 5, 10, 3]

마지막 요소를 삭제하고 그룹의 크기를 줄입니다

         9 (0)
       /   \
 (1)  5     10 (2)

  arr = [9, 5, 10, 3]
  heap_size -= 1
  arr.pop()

그래서 어레이는

  arr = [9, 5, 10]

뿌리에서 기포

9>5이기 때문에 교환하기 때문에:

         5 (0)
       /   \
 (1)  9     10 (2)

  arr = [5, 9, 10]

3.python에서 삭제된 실현

python의 거품 구현

    def bubbleDown(self):
        # the index of the root => 0
        i = 0
        while True:
            smallest = None

            leftChildIndex = self.getLeftChildNodeIndex(i)
            rightChildIndex =  self.getRightChildNodeIndex(i)
            #  if the node has not any child 
            if (not self.hasLeftChild(i) and not self.hasRightChild(i)):
                break
            # if the node has only a left child
            elif (not self.hasRightChild(i)):
                # the smallest variable will be the index of the left child
                smallest = leftChildIndex
            # if the node has only a right child
            elif (not self.hasLeftChild(i)):
                # the smallest variable will be the index of the right child
                smallest = rightChildIndex
            # if the node has 2 children
            else:
                # the smallest variable will be the smallest value of the 2 children
                smallest = rightChildIndex if self.heap[rightChildIndex] < self.heap[leftChildIndex] else leftChildIndex            
            # if the node's value is greater than its one of children
            if (self.heap[i] > self.heap[smallest]):
                # swap the node with its child
                self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
                # the i variable will be the index of the smallest value of the two children
                i = smallest
            # if the node's value is smaller than its one of children
            else:
                break
        return

python에서 실행 삭제

    def delete(self):
        # if the size the heap is one or the heap is empty(size = 0)
        if self.heap_size <= 1:
            self.heap = []
            return
        # replace last element with the root
        self.heap[self.heap_size - 1], self.heap[0] = self.heap[0], self.heap[self.heap_size - 1]
        # decrease the size of heap
        self.heap_size -= 1
        # delete last element
        self.heap.pop()
        self.bubbleDown()

python의 무더기 구현 (최종 코드)

class MinHeap:
    def __init__(self):
        self.heap = []
        self.heap_size = 0

    def getParentNodeIndex(self, i: int) -> int:
        return (i-1)//2

    def getLeftChildNodeIndex(self, i: int) -> int:
        return 2*i+1

    def getRightChildNodeIndex(self, i: int) -> int:
        return 2*i+2

    def hasParent(self, i: int) -> bool:
        # cheking if a node has a parent
        return self.getParentNodeIndex(i) < len(self.heap)

    def hasLeftChild(self, i: int) -> bool:
        # cheking if a node has a left child
        return self.getLeftChildNodeIndex(i) < len(self.heap)

    def hasRightChild(self, i: int) -> bool:
        # cheking if a node has a right child
        return self.getRightChildNodeIndex(i) < len(self.heap)

    def getMinValue(self) -> int:
        """
            time complexity => O(1)
        """
        return self.heap[0]

    def insert(self, value: int):
        self.heap_size += 1
        # insert the element at the end
        self.heap.append(value) 
        # bubble up the new element
        self.bubbleUp(len(self.heap) - 1)

    def bubbleUp(self, i: int):
        parentIndex = self.getParentNodeIndex(i)
        if parentIndex < 0:
            parentIndex = 0 
        # Loops until it reaches a leaf node
        while(i > 0 and self.heap[i] < self.heap[self.getParentNodeIndex(i)]): 
            # Swap the elements
            self.heap[i], self.heap[self.getParentNodeIndex(i)] = self.heap[self.getParentNodeIndex(i)], self.heap[i]
            i = self.getParentNodeIndex(i) 

    def delete(self):
        # if the size the heap is one or the heap is empty(size = 0)
        if self.heap_size <= 1:
            self.heap = []
            return
        # replace last element with the root
        self.heap[self.heap_size - 1], self.heap[0] = self.heap[0], self.heap[self.heap_size - 1]
        # decrease the size of heap
        self.heap_size -= 1
        # delete last element
        self.heap.pop()
        self.bubbleDown()

    def bubbleDown(self):
        # the index of the root => 0
        i = 0
        while True:
            smallest = None

            leftChildIndex = self.getLeftChildNodeIndex(i)
            rightChildIndex =  self.getRightChildNodeIndex(i)
            #  if the node has not any child 
            if (not self.hasLeftChild(i) and not self.hasRightChild(i)):
                break
            # if the node has only a left child
            elif (not self.hasRightChild(i)):
                # the smallest variable will be the index of the left child
                smallest = leftChildIndex
            # if the node has only a right child
            elif (not self.hasLeftChild(i)):
                # the smallest variable will be the index of the right child
                smallest = rightChildIndex
            # if the node has 2 children
            else:
                # the smallest variable will be the smallest value of the 2 children
                smallest = rightChildIndex if self.heap[rightChildIndex] < self.heap[leftChildIndex] else leftChildIndex            
            # if the node's value is greater than its one of children
            if (self.heap[i] > self.heap[smallest]):
                # swap the node with its child
                self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
                # the i variable will be the index of the smallest value of the two children
                i = smallest
            # if the node's value is smaller than its one of children
            else:
                break
        return

    def printAll(self):
        print(self.heap)

my_heap = MinHeap()
my_heap.insert(5)
my_heap.insert(10)
my_heap.insert(1)
my_heap.insert(2)
my_heap.insert(3)
my_heap.insert(4)
#      1
#    /  \ 
#   2     4
#  / \   /
# 10  3  5
my_heap.printAll()
my_heap.delete()
my_heap.printAll()
#      2
#    /  \ 
#   3     4
#  / \   
# 10  5  
print(my_heap.heap_size) # 5
print(my_heap.getMinValue()) # 2

참고 자료와 유용한 자원

https://www.geeksforgeeks.org/array-representation-of-binary-heap/

https://blog.devgenius.io/how-to-implement-a-binary-heap-javascript-d3a0c54112fa

https://www.section.io/engineering-education/heap-data-structure-python/

https://en.wikipedia.org/wiki/Heap_(data_structure)#:~:text=In%20computer%20science%2C%20a%20heap,to%20the%20key%20of%20C.

다음 글에 대한 조언이나 질문이 있으면 저에게 연락 주세요telegram
해피 코딩:)
#22일차