힙 정렬 실습

 

In [1]:

#22강 힙
'''힙이란?
1 루트 노드가 언제나 최대 또는 최소값을 가짐
-최대힙, 최소힙

2 완전 이진 트리여야함

최대힙(모든 노드가 부모가 자식보다 큼)
       30      
    24    12   
 18   21  8  6  
4  2 19 

이진 탐색 트리와의 비교
1 원소들은 완전히 크기 순으로 정렬됐나? -> no
2 특정 키 값을 가지는 원소를 빠르게 검색하는가?->no
3 부가 제약 조건이 있는가? -> 완전 2진트리여야 함

최대 힙의 추상적 자료구조
연산의 정의
__init__()-빈 최대 힙을 생성
insert(item)-새로운 원소를 삽입
remove()-최대 원소(root)를 반환(동시에 이 노드 삭제)

데이터 표현의 설계
배열을 이용한 이진 트리의 표현
       30                1
    24    12        2        3
 18   21  8  6   4     5   6   7
4  2 19         8  9 10
노드번호 m을 기준으로
왼쪽 자식의 번호: 2m
오른쪽 자식의 번호:2m+1
부모 노드의 번호 : m//2

완전 이진 트리이므로:노드의 추가/삭제는 마지막 노드에서만

배열로 표현(완전 이진트리(두개씩 있어)라 가능)
0 none
1 30
2 24
3 12
4 18
5 21
6 8
7 6
8 4
9 2
10 19
최대 힙에 원소 삽입- 복잡도
원소의 개수가 n인 최대 힙에 새로운 원소 삽입
-> 부모 노드와의 대소 비교 최대 회수 : log 2 n [O(log n)]
'''
#22강 실습: 최대 힙에 새로운 원소 삽입
class MaxHeap:
    def __init__(self):
        #0번 인덱스는 none
        self.data = [None]

    def insert(self, item):
        #끝에서 부터 시작
        curr=len(self.data)
        #
        self.data.append(item)
        while curr>1:
            if self.data[curr//2]<self.data[curr]:
                self.data[curr],self.data[curr//2]=self.data[curr//2],self.data[curr]
            curr=curr//2
    
def solution(x):
    return 0

 

In [ ]:

#23강 힙
'''최대 힙의 원소의 삭제
1 루트 노드의 제거- 이것이 원소들 중 최대값
but 루트노드가 빈자리면 이진트리의 구조가 파괴됨
2 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
3 더큰 자식 값과 자리를 계속 바꿔감
-자식은 둘 있을 수도 있는데, 어느 쪽으로 이동?

      20      
    6    12   
  2   4 
루트노드 20 제거
그자리에 4 삽입
      4       
    6    12   
  2     
자식들과 크기 비교후 12와 바꿈
      12       
    6    4 
  2  

복잡도 : 원소의 개수가 n인 최대 힙에서 최대 원소 삭제
-> 자식 노드들과의 대소 비교 최대 회수 :2 log 2 n [O(logn)]

최대/최소 힙의 응용
1 우선 순위 큐
-enqueue 할 때 '느슨한 정렬'을 이루고 있도록함 :O(logn)
-Dequeue 할 때 최대값을 순서대로 추출 :O(logn)
2 힙 정렬
-정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 O(logn)
-삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제 O(logn)
-원소들이 삭제된 순서가 원소들의 정렬순서
-정렬 알고리즘의 복잡도 O(logn)

def heapsort(unsorted):
    H=MaxHeap()
    for item in unsorted:
        H.insert(item)
    sorted=[]
    d=H.remove()
    while d:
        sorted.append(d)
        d=H.remove()
    return sorted
'''
#23강 실습: 최대 힙에서의 원소 삭제
class MaxHeap:

    def __init__(self):
        self.data = [None]


    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data


    def maxHeapify(self, i):
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = 2*i

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = 2*i+1

        smallest = i
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[left]>self.data[smallest]:
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            smallest=left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right< len(self.data) and self.data[right]>self.data[smallest]:
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            smallest=right

        if smallest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i],self.data[smallest]=self.data[smallest],self.data[i]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(smallest)


def solution(x):
    return 0