# Heap

- Heap 은 가장 먼저 배우는 것은 Binary Heap 이다. Binary Heap 은 min heap 과 max heap 두 가지로 나눠질 수 있는데 min heap 은 가장 작은 값이 root 인 것이고, max heap 은 가장 큰 값이 root 인 heap 을 의미한다.
- Heap 의 가장 큰 장점은 Max / Min 값을 찾는데 $O(1)$ 의 시간 밖에 걸리지 않는다는 것이다. 그래서 K번째 큰 수와 같은 문제에서 사용될 수 있다.
- Heap 의 특징은 특정 key 값을 검색하는데는 잘 사용하지 않는다는 것이다. 물론 값을 하나씩 pop 하면서 원하는 값이 나올 때까지 반복해야한다고 하지만, 이는 비효율적이기 때문에 이런 경우에는 다른 자료구조를 사용해야한다. 얘기했던 것처럼 heap 이라는 자료구조는 max 또는 min 값을 찾는데 유용한 자료구조이기 떄문이다.
- Heap 에는 push, pop, peek 과 같은 기능들이 있는데, push 하는 것은 log N 의 시간을, pop 하는 것 또한 log N 의 시간이 소요되기 때문에 빠른 편이라고 생각할 수 있다.
- 이러한 점을 이용해서 Heap Sort 라는 정렬 방식도 있는데, key를 binary heap 에 push하고, pop을 하게 되면 pop 한 결과가 자동으로 정렬된 형태로 튀어나온다. min heap을 이용하면 오름차순 정렬이, max heap을 사용하면 내림차순 정렬이 된다.
- Binary Heap의 강점은 다름아닌 우선순위 큐를 만들 수 있다는 것이다. 데이터를 우선순위에 따라서 저장할 필요가 있을 때, $O(1)$의 탐색 시간과 $O(log N)$의 heapify 하는 시간 복잡도를 갖는다. (때때로, lazy update를 통해서 pop 을 할 때, 나중에 빼도 된다.)

### 나의 구현

class MinHeap:

    def __init__(self):
        """
        heap starts from index 1, not 0
        data can be tuple, class or other data type (here, only integer)
        """
        
        self.heap = [0]

    def __compare(self, c1, c2):
        """
        can be used for comparing priority
        """
        
        return self.heap[c1] < self.heap[c2]

    def __up(self, cursor):
        """
        from start cursor to root, swap with parent
        """
        
        p = cursor // 2
        while p >= 1:
            if self.__compare(cursor, p):
                self.heap[cursor], self.heap[p] = self.heap[p], self.heap[cursor]
                cursor = p
                # update parent
                p = cursor // 2
            else:
                break

    def __down(self, cursor):
        """
        from start cursor to leaf, swap with child
        """
        
        while 2*cursor <= len(self.heap)-1:
            lc, rc = 2*cursor, 2*cursor + 1
            
            # select left child or right child
            if rc <= len(self.heap)-1:
                child = lc if self.__compare(lc, rc) else rc
            else:
                child = lc
            # swap
            if self.__compare(child, cursor):
                self.heap[cursor], self.heap[child] = self.heap[child], self.heap[cursor]
                
            # update cursor
            cursor = child

    def push(self, key):
        """
        add key to heap and update heap 
        """
        self.heap.append(key)
        self.__up(len(self.heap)-1)

    def pop(self):
        """
        remove the first key and replace the last element
        """
        
        popkey = self.heap[1] if len(self.heap)-1 > 0 else -1
        self.heap[1] = self.heap[len(self.heap)-1]
        del self.heap[len(self.heap)-1]
        self.__down(1)
        return popkey
    
def main():
    h = MinHeap()
    import random

    for _ in range(1):
        h.push(random.randint(-100, 100))

    print ("heap sort result: ")
    while len(h.heap)-1 > 0:
        print(h.pop(), end=" ")
    print()

if __name__ == "__main__":
    main()

### 다른 구현
참고: https://runestone.academy/ns/books/published/pythonds/Trees/BinaryHeapImplementation.html

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0


    def percUp(self,i):
        while i // 2 > 0:
          if self.heapList[i] < self.heapList[i // 2]:
             tmp = self.heapList[i // 2]
             self.heapList[i // 2] = self.heapList[i]
             self.heapList[i] = tmp
          i = i // 2

    def insert(self,k):
      self.heapList.append(k)
      self.currentSize = self.currentSize + 1
      self.percUp(self.currentSize)

    def percDown(self,i):
      while (i * 2) <= self.currentSize:
          mc = self.minChild(i)
          if self.heapList[i] > self.heapList[mc]:
              tmp = self.heapList[i]
              self.heapList[i] = self.heapList[mc]
              self.heapList[mc] = tmp
          i = mc

    def minChild(self,i):
      if i * 2 + 1 > self.currentSize:
          return i * 2
      else:
          if self.heapList[i*2] < self.heapList[i*2+1]:
              return i * 2
          else:
              return i * 2 + 1

    def delMin(self):
      retval = self.heapList[1]
      self.heapList[1] = self.heapList[self.currentSize]
      self.currentSize = self.currentSize - 1
      self.heapList.pop()
      self.percDown(1)
      return retval

    def buildHeap(self,alist):
      i = len(alist) // 2
      self.currentSize = len(alist)
      self.heapList = [0] + alist[:]
      while (i > 0):
          self.percDown(i)
          i = i - 1

bh = BinHeap()
bh.buildHeap([9,5,6,2,3])

print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())