✍️오늘 공부한 내용

• 힙소트,힙 만들기
• heapq
• 백준 문제
  • 1655 가운데를 말해요
  • 1715 큐 카드 정렬하기
    

📋새로 배우게 된 내용

• 최소 최대 힙에서 트리는 완전트리여야한다.

정답: (O)/(O)/(X)/(O)/(O)/(X)

• 핵심은 왼쪽자식노드의 맨마지막이 비어있으면서 오른쪽이 있으면 안되거나 오른쪽 자식노드의 맨마지막의 왼쪽이 비어있으면서 오른쪽값이 있으면 안된다.
• 배열로 표시한다면

• 참고

def heapify(x):
    """Transform list into a heap, in-place, in O(len(x)) time."""
    n = len(x)
    # Transform bottom-up.  The largest index there's any point to looking at
    # is the largest with a child index in-range, so must have 2*i + 1 < n,
    # or i < (n-1)/2.  If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
    # j-1 is the largest, which is n//2 - 1.  If n is odd = 2*j+1, this is
    # (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
    for i in reversed(range(n//2)):
        _siftup(x, i)

😝느낀점

• 다시 힙소트를 복습하는데 어제 배웠던 거랑 내용이 달라서 다시 한번 확인하기로 했는데, heapq.heappush()랑 heap.heappop()랑 heapq.heapify()를 헷갈렸던 거 같음. 두 개는 O(logN) 시간복잡도이고 heapify()로는 O(N)만큼 걸린다. heapify()는 리스트를 만들어주는 거기도 하고..

👊다짐

• 공식 문서 확인 필수!!
  [파이썬 heapq.py 라이브러리 github]

🚀오늘의 한줄평

• 힙소트와 한 노드 가까워지기 day2🗓️