Heap tree ( Insert, find_max, delete_max )

힙트리에서의 Insert, find_max, delete_max 를 알아보기전에 make heap tree 부분을 먼저 보고 공부해보시길 추천합니다. 👏🏻

https://p-james-y.tistory.com/16

Heap tree 만들기 ( make heap )

1. Insert

노드를 Insert 를 하는데 힙 성질을 만족하도록 삽입한다.

아래 그림과 같이 힙 성질을 만족하는 트리가 있다고 하자. 

배열과 힙트리

여기에 Insert(15) [ 노드 15 를 맨 마지막 리프노드로서 삽입 ] 한다.

Insert(15)

이제 노드 15번을 heapify up 을 하며 힙성질을 만족하는 힙트리로 재배치 해야 한다.

노드 15와 노드 10을 비교해보면 노드 15가 부모 노드인 노드 10보다 크므로 노드 15와 노드 10을 스와핑 해준다.

노드15 와 노드10 스와핑

노드 15와 노드 15의 부모노드인 노드 13을 비교한다. 노드 15보다 노드 13 이 값이 작으므로 스와핑 해준다.

노드15와 노드13 스와핑

마지막으로 루트노드 14와 노드 15를 비교한다. 노드 15가 루트노드인 노드 14보다 크므로 스와핑 해준다.

노드15와 노드14 스와핑

이렇게 노드 15를 삽입한결과 힙성질을 만족하는 트리가 완성된다.

정리를 하자면 인서트로 맨 마지막 리프노드로 추가한다음에 heapify up 을 통해 인서트된 노드를 힙성질이 만족하는 힙트리가 되게끔 위로 이동 시켰다. 시간복잡도는 최악의 경우 리프노드부터 루트노드까지 확인해야 할수 있으므로 트리의 높이 (h) 인 O(logN) 이다. 코드로 확인해보자

def heapify_up(node_index): # H[node_index] 를 heapify up
    while node_index > 0 and H[(node_index-1)//2] < H[node_index] # 부모노드의 키값이 자기 노드의 키값보다 작고 루트노드 까지
        H[node_index], H[(node_index-1)//2] =  H[(node_index-1)//2], H[node_index]
        node_index = (node_index - 1) // 2
	

def insert(node):
    H.append(node)
    H.heapify_up(node_index) # H[node_index] 를 루트 노드까지 이동하면서 heapify

힙트리를 만들때 비교 표

	make heap	insert
시간 복잡도	O(N)	Nlog(N) 👉  heapify up 을 노드 갯수 만큼 실행

2. Find_max 

힙트리에서 가장 큰수는 루트노드에 있다. 시간복잡도는 O(1) 이 된다.

def find_max():
    return H[0]

단순히 루트노드를 return 하면 된다.

3. Delete_max

가장 먼저 루트노드가 가장 큰 값이기 때문에 루트노드를 pop 해주면 된다. 하지만 그냥 pop 해버리면 루트노드가 없어지기 때문에 가장 마지막 리프노드와 루트 노드를 먼저 스와핑 해준다음에 마지막 리프노드로 이동한 루트노드를 pop 해준다. 그리고 현재의 루트노드를 heapify down 을 통해 위치를 재정의 해준다. 코드로 정리해보자.

 

 

heapify down(히피파이 다운을 할 인덱스, 힙의 갯수)

def delete_max:
    if len(A) == 0: # 만약에 빈 힙이면 
        return None
    key = A[0] # 현재의 루트노드를 key 에 저장해둔다.
    A[0], A[len(A)-1] = A[len(A)-1], A[0] # 루트노드와 가장 마지막 리프노드를 스와핑 해준다.
    A.pop() # 마지막 인덱스의 값이 없어짐
    heapify_down(0, len(A)) # 0번 인덱스 즉 루트노드부터 heapify down 을 해준다.
    return key # 최대 값 노드를 반환한다

4. 시간복잡도 정리

	시간복잡도
make heap	O(N), O(NlogN)
insert	O(logN)
find max, find min	O(1)
delete max, delete min	O(logN)
heapify down	O(logN)
heapify up	O(logN)

Reference

https://www.youtube.com/watch?v=6VMSTOdHRfI&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=22