트리(Trees)

1. 트리의 정의 및 특징

트리는 스택, 큐와는 달리 2차원의 자료구조로, 정점(node, 노드)와 간선(edge, 에지)을 이용해 데이터의 배치 형태를 추상화한 자료구조이다. 노드는 다른 노드와 에지로 연결될 수 있다.

2. 트리의 구성요소

• 정점(node): 데이터를 직접적으로 담고 있는 요소
• 간선(edge): 노드를 잇는 연결선
• 뿌리(root) 노드: 최상위 노드로, 부모 노드가 없이 자식 노드만 가질 수 있다.
• 잎(leaf) 노드: 최하위 노드로, 자식 노드가 없다.
• 내부(internal) 노드: 뿌리도 잎도 아닌 노드
• 부모(parent) 노드: 위아래로 연결된 두 노드 중 뿌리 쪽에 가까운 노드
• 자식(child) 노드: 위아래로 연결된 두 노드 중 잎 쪽에 가까운 노드
• 형제(sibling) 노드: 같은 부모를 가진 노드들
• 조상(ancestor): 부모의 부모를 타고 가며 만나는 노드들
• 후손(descendant): 자식의 자식을 타고 가며 만나는 노드들

3. 트리에서 특수한 정의

수준(level)은 거쳐가는 간선의 개수가 늘어날 수록 커지는 수로, 루트 노드는 0이고, 잎 쪽으로 자식을 내려갈 수록 1씩 더한다. 가끔 루트 노드는 1이라고 하기도 한다. 루트 노드의 수준을 0으로 시작하면, level = (해당 노드에 도달하기 위해 거쳐야 하는 간선 수)가 성립한다.

트리의 높이(height) 혹은 깊이(depth)는 (가장 높은 level) + 1으로 표현할 수 있다.

부분 트리(subtree)는 특정 노드를 새로운 루트 노드를 하는 트리이다.

노드의 차수(degree)는 자식(서브트리)의 수를 말한다. 차수가 0이면 leaf 노드에 해당하며, 루트 노드를 제외하면 모든 노드는 parent로 가는 간선은 오직 하나이다.

이진 트리(binary tree)

1. 이진 트리의 정의 및 특징

이진 트리는 모든 노드의 차수가 2 이하인 트리를 말한다.

이진 트리는 재귀적으로 정의할 수 있다.
노드는 빈 트리이거나 ‘루트 노드 + 왼쪽 노드(서브트리) + 오른 노드(서브트리)’로 이루어져 있다. 왼쪽과 오른쪽 서브트리 또한 이진트리이다.

자식을 하나씩 두고 한 줄로 쭉 이어진 형태 또한 이진트리이다.

2. 포화 이진 트리(full binary tree)

모든 레벨에서 노드들이 모두 채워져 있는 이진트리를 일컫는다. 높이가 k라면 노드 개수는 $2^k – 1$개이다.

3. 완전 이진 트리(complete binary tree)

높이가 k인 완전이진트리라 하면, 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화이진트리이고, 레벨 k-1에서는(마지막) 왼쪽부터 노드가 순차적으로 채워져 있는 이진트리이다.

4. 이진 트리의 연산

• size(): 현재 트리에 포함된 노드의 수
• depth(): 트리의 깊이(높이)
• traversal: 트리를 순회함

5. 이진트리의 구현

1) 노드: 값인 data item, 각각 왼쪽과 오른쪽 자식인 left child, right child를 요소로 갖는다.
2) 트리: root노드를 요소로 가진다.
3) size() 함수
재귀적 방법으로 구할 수 있다.
리턴하는 값은 (왼 노드의 사이즈) + (오른 노드의 사이즈) + 1이다. 1을 더해주는 이유는 자기 자신까지 포함하기 위함이다.
단, 이 경우는 왼쪽이나 오른쪽 노드가 있을 때만 해당하며 없을 때는 size를 0으로 계산한다.
재귀 함수의 시작은 루트 노드에서 호출하고, 루트 노드가 없으면 빈 트리란 뜻이므로 0 반환한다.
4) depth() 함수
역시 재귀적으로 구할 수 있다. (왼쪽 depth와 오른쪽depth 중 더 큰 값) + 1이다. 마지막에 1을 더해주는 이유는, 본인이 부모 노드이기 때문에 깊이가 1 증가해줘야 하기 때문이다.

class Node:
    def __init__(self, item):
        self.data = item
        self.left = None  # 왼쪽 자식
        self.right = None  # 오른쪽 자식

	# 해당 노드를 루트로 하는 서브트리의 크기. 재귀적으로 사용함
    def size(self):
		# 만약 왼/오른 자식이 없다면 0으로 함
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1  # 자기 자신을 포함하므로 1 더해줌

	# 해당 노드를 루트로 하는 서브트리의 깊이. 재귀적으로 사용함.
    def depth(self):
    	# 만약 왼/오른 자식이 없다면 0으로 함
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return max(l, r) + 1  # 왼쪽과 오른쪽 중 더 큰 값으로 사용하며, 자기 자신을 포함하므로 1을 더해줌


class BinaryTree:
    def __init__(self, r):
        self.root = r

    # 트리 전체의 크기
    def size(self):
    	# 루트 노드로부터 시작하며, 루트 노드가 없으면 빈 트리이므로 0 반환
        if self.root:
            return self.root.size()
        else:
            return 0

	# 트리 전체의 깊이
    def depth(self):
    	# 루트 노드로부터 시작하며, 루트 노드가 없으면 빈 트리이므로 0 반환
        if self.root:
            return self.root.depth()
        else:
            return 0

6. 이진트리의 순회

이진 트리의 순화는 다음과 같이 나뉜다.

• 깊이 우선 순회(depth first traversal, DFT)
  • 중위 순회(in-order): 왼-나-오
  • 전위 순회(pre-order): 나-왼-오
  • 후위 순회(post-order): 왼-오-나
• 넓이 우선 순회(breadth first traversal, BFT)

순회는 기본적으로 왼쪽에서 오른쪽 순서로 진행한다.

깊이 우선 순회는 현재 위치한 노드(나)와 양쪽 자식 노드 간의 관계에 기반하여 움직이며, 아래로 점점 내려가므로 ‘깊이’의 개념으로 이해한다.
중위 순회는 왼 자식 – 나 – 오른 자식 순으로, 전위 순회는 나 – 왼 자식 – 오른 자식, 후위 순회는 왼 자식 – 오른 자식 – 나 순으로 방문한다. 즉 나를 언제 방문하는가를 기준으로 살핀다.

넓이 우선 순회는 수준이 낮은 노드를 우선으로 방문하며, 같은 수준 노드들 사이에선 부모 노드의 방문 순서에 따라 방문한다.

1) 깊이 우선 순회의 구현

class Node:
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None

	# 중위 순회
    def inorder(self):
        traversal = []  # 순회하는 노드의 값을 담을 빈 배열
        # 왼쪽
        if self.left:
            traversal += self.left.inorder()  # 다시 재귀적으로 호출
        # 자기 자신
        traversal.append(self.data)
        # 오른쪽
        if self.right:
            traversal += self.right.inorder()  # 다시 재귀적으로 호출
        return traversal

	# 전위 순회
    def preorder(self):
        traversal = []
        # 자기 자신
        traversal.append(self.data)
        # 왼쪽
        if self.left:
            traversal += self.left.preorder()
        # 오른쪽
        if self.right:
            traversal += self.right.preorder()
        return traversal
        
     # 후위 순회
     def postorder(self):
        traversal = []
        # 왼쪽
        if self.left:
            traversal += self.left.postorder()
        # 오른쪽
        if self.right:
            traversal += self.right.postorder()
        # 자기 자신
        traversal.append(self.data)
        return traversal

class BinaryTree:

    def __init__(self, r):
        self.root = r

    # 트리 전체 중위 순회: 루트부터 시작
    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

    # 트리 전체 전위 순회: 루트부터 시작
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []
            
    # 트리 전체 후위 순회: 루트부터 시작
	def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

2) 넓이 우선 순회의 구현
깊이 우선 순회와는 달리 재귀적 방법은 적합하지 않다. 한 노드를 방문했을 때 나중에 방문할 노드들을 순서대로 기록해두어야 하는데, 이는 큐를 이용하면 좋다.
왼쪽 자식과 오른쪽 자식을 큐에 넣고, 큐 첫 원소 뽑아 방문한다. 해당 과정을 반복하면 한 레벨이 끝날 때 다음 레벨에 방문해야 할 순서가 큐에 남아 있다.
큐가 비어있으면 모든 노드의 순회가 끝났으므로 알고리즘을 종료한다.

## 배열 큐
class ArrayQueue:
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]

## 큐에 들어갈 각 노드
class Node:
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None

## 전체 이진 트리
class BinaryTree:
    def __init__(self, r):
        self.root = r

	## 넓이 우선 순회
    def bft(self):
    	# 순회 순서를 담을 배열과 다음 레벨의 순서를 담을 빈 큐 선언
        traverse = []
        q = ArrayQueue()
        
        if self.root:
            q.enqueue(self.root) # 루트 노드를 우선 큐에 넣고 시작
            while not q.isEmpty():  # 큐에 남은 요소가 없을 때까지(다음 레벨을 다 소진할 때까지) 반복함
                curr = q.dequeue()  # 큐에서 요소를 빼냄
                traverse.append(curr.data)  # 순회 리스트에 넣음
                if curr.left:  # 왼쪽 자식이 있으면 큐에 넣음
                    q.enqueue(curr.left)
                if curr.right:  # 오른쪽 자식이 있으면 큐에 넣음
                    q.enqueue(curr.right)
            return traverse
        else:
            return []

이진 탐색 트리(binary search tree)

1. 이진 탐색 트리의 정의 및 특징

모든 노드에 대해 왼쪽 서브트리 데이터는 현재 노드보다 작고 오른쪽 서브트리 데이터는 현재 노드보다 큰 이진트리를 말한다. 이때 중복 데이터 원소는 없는 것으로 가정한다. 이진 탐색 트리는 데이터 검색에 유용하다.

이진 탐색 트리는 ‘정렬된 배열을 이용한 이진 탐색’과 비슷하다.
이진 탐색 트리를 사용할 경우 이진 탐색보다 데이터 원소의 추가와 삭제가 용이하다. 배열의 경우에는 원소를 끼워넣고 빼며 빈 공간을 만들고 없애는 데 시간이 오래 걸리기 때문이다. 대신 공간의 소요는 더 크다.
이진 탐색 트리는 대게 $O(\mathrm{log}n)$의 탐색 복잡도를 가지긴 하지만 항상 그렇지는 않음

2. 이진탐색트리의 데이터와 연산

데이터는 (key, value) 쌍으로 표시할 수 있다. key는 노드의 고유한 숫자로, 탐색의 기준이 된다. value는 사람 이름인 등 해당 노드가 가진 실질적 값을 말한다.

• insert(key, data): 트리에 주어진 데이터 원소를 추가함.
• remove(key): 특정 원소 삭제
• lookup(key): 특정 원소 검색
• inorder(): 키 순서대로 원소 나열. 이진 탐색이기 때문에 중위 순회함.
• min() / max(): 최소/최대 키를 가지는 원소 탐색

이진 탐색 트리에 원소를 삽입할 땐, 루트부터 시작하여 원소 값이 탐색중인 노드의 키보다 작으면 왼쪽으로, 크면 오른쪽으로 이동하며, 최종적으로는 잎으로 달리게 된다. 키의 중복은 없거나 있다면 KeyError을 일으킨다고 가정한다.

최솟값을 구하는 연산 시에는 재귀 함수로서 왼쪽(더 작은 값)을 따라가다 왼쪽 자식이 존재하지 않을 때 본인을 리턴한다. 최댓값을 구할 때는 그 반대로 오른쪽을 타고 가면 된다.

특정 원소를 검색하는 연산 lookup()의 경우, 출력으로 결과 노드와 그 부모 노드까지 리턴하는데, 부모 노드까지 필요한 이유는 원소 삭제에 필요하기 때문이다.

remove()를 제외한 구현은 다음과 같다.

class Node:
    def __init__(self, key, data):
    	# key & value(data)를 각각 선언함
        self.key = key
        self.data = data
        self.left = None
        self.right = None

	# 해당 노드 위치를 기준으로 (key)의 값을 가지는 요소를 삽입
    def insert(self, key, data):
    	# 입력값과 해당 노드 키 비교해 좌/우로 움직임
        if self.key > key:
            if self.left:
                self.left.insert(key, data)  # 밑으로 자식이 더 있으므로 insert 재귀 호출
            else:
                self.left = Node(key, data)  # 잎 노드이므로 여기에 달아둠
            return True
        elif self.key < key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
            return True
        else:
        	# 해당 노드와 입력할 키가 같다 = 키 중복 이므로 에러임
            raise KeyError

	# 키 값으로 해당 노드와 그 부모를 찾아냄.
    def lookup(self, key, parent=None):
        if key < self.key:
            if self.left:
                return self.left.lookup(key, self)
                	# 왼쪽 노드를 더 타고가야 함. 
                    # 밑으로 내려가면 본인이 parent되므로 두 번째 인자에 self를 넣음
            else:
                return None, None  # 찾으려는 노드가 없음
        elif key > self.key:
            if self.right:
                return self.right.lookup(key, self)
            else:
                return None, None
        else:
            return self, parent  # 노드를 찾음

    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal

	# 해당 노드의 자식의 수를 셈. remove() 연산을 위함.
    def countChildren(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count
        
        
class BinSearchTree:
    def __init__(self):
        self.root = None

	# 트리에 특정 원소를 삽입함. 루트 노드부터 시작
    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)  # 빈 트리이므로 해당 노드를 루트로 삼음

	# 트리에서 특정 원소를 검색함. 루트 노드부터 시작
    def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None

    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

3. 이진 탐색 트리의 원소 삭제

삭제는 두 가지 프로세스로 구성된다.
(1) 키를 이용해 노드를 찾기
(2) 찾은 노드 제거하고도 이진 탐색 트리의 성질을 유지하도록 트리 구조 정리하기

(1)에서는 해당 키 노드가 없으면 삭제할 것도 없으며, 노드를 찾았을 땐 그 노드의 부모도 알고 있어야 한다. 이 이유는 (2)에 있다.
(2)에서는 삭제하려는 노드가 아래 3가지 경우 중 무엇인지 따져야 한다.

(가) 잎 노드인 경우: 해당 노드가 부모 노드의 어느 쪽 자식이었는지 알아내 그쪽을 None으로 처리(링크 끊기)하면 된다. 단 삭제되는 노드가 root인 경우는 트리 자체가 없어져야 한다.
(나) 자식을 하나 가진 경우: 자식이 어느 쪽에 붙은 자식인지, 또한 본인은 부모 노드의 어느 쪽 자식인지 알아내 부모 노드와 본인의 자식 노드를 이어주어야 한다. 삭제되는 노드가 루트인 경우, 대신 들어오는 자식이 새로 root가 됨에 주의한다.
(다) 자식을 둘 가진 경우: 계승자(successor)을 찾아야 한다. 여기서는 삭제되는 노드보다 바로 다음 큰 키를 가지는 노드를 계승자라 하자. 즉, 오른 자식의 서브트리 중 가장 작은 노드를 말한다. 이 계승자를 찾아 삭제되는 노드 자리에 대신 배치하고 계승자의 원래 위치의 노드를 삭제한다. 계승자의 원래 부모 노드를 par라고 하면 par의 왼쪽 링크를 조절해줘야 한다. 단, 계승자가 삭제하려는 노드의 바로 오른쪽 자식이라 삭제 노드가 곧 계승자의 부모 노드인 경우, 특수하게 par의 오른쪽 링크를 조절해야 한다.

4. 이진 탐색 트리의 원소 삭제 구현

위에서 이미 구현한 부분은 #######생략#######라고 표시했다.

class BinSearchTree:

#######생략#######

    def remove(self, key):
        node, parent = self.lookup(key)  # 삭제할 노드를 찾아냄
        # 찾은 노드가 있다면
        if node:
            nChildren = node.countChildren()  # 자식의 수를 셈
            
            # (가) 자식이 없음. 본인이 잎 노드임
            if nChildren == 0:
                if parent:
                	# 만약 parent가 있으면 본인이 왼/오른자식인지 알아내
                    # 부모 노드의 링크를 조정함
                    if parent.left == node:
                        parent.left = None
                    else:
                        parent.right = None
                else: # 만약 parent 가 없으면 (node 는 root 인 경우)
                    self.root = None  # 빈 트리로 만듦
                    
            # (나) 자식이 하나 있음.
            elif nChildren == 1:
                # 자식을 child라고 일단 가리킴
                if node.left:
                    child = node.left
                else:
                    child = node.right
                # 만약 parent가 있으면 본인이 왼/오른자식인지 알아내
                # child와 parent을 이음
                if parent:
                    if parent.left == node:
                        parent.left = child
                    else:
                        parent.right = child
                # 만약 parent 가 없으면 (node가 root 인 경우)
                # 루트를 child로 함
                else:
                    self.root = child
                    
            # (다) 자식이 둘인 경우
            else:
            	# 일단 parent(최종 계승자의 부모가 될 것)는 삭제할 노드로, 
                # successor(최종 계씅자가 될 것)은 삭제할 노드의 오른 자식으로 설정함
                parent = node
                successor = node.right
                # 계승자의 왼쪽 노드를 따라가며 진짜 계승자 노드를 찾아냄
                while successor.left:
                    parent = successor  # 지금 계승자를 부모로
                    successor = successor.left  # 왼쪽(작은 값)을 계승자로
                # 반복문이 끝났으므로 계승자를 찾은 것. key와 데이터를 node에 덮어씀
                node.key = successor.key
                node.data = successor.data
                # 계승자가 제 부모의 왼쪽/오른쪽 자식인지를 판단해 연결을 마침
                # 계승자는 왼쪽 자식이 없음
                if parent.left == successor:
                    if successor.right:
                        parent.left = successor.right
                    else:
                        parent.left = None
                else:
                    if successor.right:
                        parent.right = successor.right
                    else:
                        parent.right = None   
            return True
		# 삭제할 노드가 없을 때
        else:
            return False

5. 이진 탐색 트리가 비효율적인 경우

이진 탐색 트리는 트리의 높이가 양쪽으로 균형적이지 못할 때 비효율적이다. 극단적으로 트리하 한 줄로 자식이 이어진 경우 선형 탐색과 동등한 복잡도를 가지게 된다.

때문에 높이의 균형을 유지해 $O(\mathrm{log}n)$의 탐색 복잡도를 보장하는 다른 트리들이 존재한다. 균형을 유지하느라 삽입/삭제가 조금은 복잡하지만 간혹 발생하는 비효율적인 경우를 처리할 수 있다. AVL tree, Red-black tree 등이 있다.

힙(Heaps)

1. 힙의 정의 및 특징

힙은 이진 트리의 한 종류로서 이진 힙(binary heap)이라고도 한다. 루트 노드가 언제나 트리 전체의 최댓값(최대힙 max heap) 혹은 최솟값(최소힙 min heap)인 완전 이진트리이다.

재귀 적으로도 정의가 가능한데, 어느 노드를 루트로 하든 그 서브 트리도 모두 최대힙인 구조를 가지고 있다.

2. 힙과 이진 탐색 트리의 비교

• 원소들의 정렬: 이진 탐색 트리는 완전히 크기 순으로 정렬되었으나, 힙에서는 다소 느슨한 정렬을 한다.
• 특정 키 값을 가지는 원소를 검색하는 속도: 이진 탐색은 왼쪽/오른쪽으로 검색하므로 빠르게 가능하나, 힙에서는 효율적 방법 없다. 순회나 검색은 힙에서 쓰지 않는다.
• 힙은 완전 이진 트리여야 한다.

3. 최대 힙의 연산 및 구현

• insert(item): 새 원소 삽입
• remove(): 최대 원소(root node) 반환 및 삭제

힙은 완전 이진 트리이므로 배열을 이용한 이진 트리의 표현이 가능하다. 노드의 번호(인덱스)를 m라 할 때 왼쪽 자식은 2m, 오른쪽 자식은 2m+1라 한다. 그렇다면 반대로 부모 노드 번호는 m//2이다. 나머지를 버리는 정수 나눗셈이다.
완전 이진 트리이므로 노드의 추가와 삭제는 마지막 노드에서만 벌어지며, 0번은 생각하지 않는다.
최대 힙에 원소를 삽입하는 insert() 연산은 다음과 같이 수행한다.

1) 트리의 가장 마지막 자리에 새로운 원소를 임시로 저장한다.
2) 부모 노드와 키 값을 비교해, 본인이 더 크다면 위로 자리를 바꾸며 이동한다.
3) 부모 노드보다 키 값이 작거나 루트라면 그 자리에서 멈춘다.

원소 삽입의 복잡도를 따져보자. 원소의 개수가 n인 최대 힙에 새로운 원소 삽입하는 경우, 움직이는 노드와 부모 노드의 대소를 비교 최대 횟수는 트리의 높이에 해당하는 $\mathrm{log_2}n$이 될 것이다. 따라서 최악의 경우 복잡도는 $O(\mathrm{log}n)$이므로 해당 속도는 최대힙의 장점이 된다.

최대 힙의 원소를 삭제하는 remove() 연산은 다음과 같이 수행한다.
1) 루트 노드의 제거한다. 이것이 원소들 중 최댓값이기 때문이다.
2) 완전 이진 트리의 모양을 다시 만들어준다. 트리의 마지막 자리 노드를 임시로 루트 노드의 자리에 배치한다.
3) 가장 큰 값을 루트로 한다는 특징을 유지해야 한다. 가장 큰 값을 트리 내에서 찾아야 하는데, 이를 위해 루트에서 시작해 자식 노드들과 값을 비교하여 아래로 자리를 바꿔가며 이동한다. 만약 자식 노드가 둘이 있으면 더 큰 값인 자식과 자리를 바꾼다.

원소 삭제의 복잡도 역시 따져볼 수 있는데, 자식 노드들과 대소를 비교하는 최대 횟수는 $2\mathrm{log_2}(n)$이다. 자식끼리 비교하고 더 큰 값과 자신을 비교하므로 상수 2가 곱해지는 것이다. 따라서 최악의 경우 복잡도는 $O(\mathrm{log}n)$이므로 이 속도 역시 최대힙의 장점이 된다.

직접 삭제 메서드를 구현할 때, 배열의 인덱스를 이용해 재귀적 방식을 사용할 수 있다.

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

    def insert(self, item):
        self.data.append(item)  # 일단 원소를 가장 마지막에 넣음
        idx = len(self.data) - 1  # 해당 원소의 인덱스를 구해둠
        # 맨 앞(가장 큰 값)을 넘지 않고, 부모 노드보다 본인이 작지 않을 때까지 반복하며 부모 노드와 자리를 바꿈
        while (idx != 1) and (self.data[idx // 2] < item):
            self.data[idx // 2], self.data[idx] = self.data[idx], self.data[idx // 2]
            idx = idx // 2  # 부모 노드의 인덱스로 변경

4. 힙의 응용

1) 우선순위 큐

• Enqueue는 느슨한 정렬 이루도록 한다. 따라서 원소의 삽입에 총 $O(\mathrm{log}n)$ 시간이 걸린다.
• Dequeue는 최댓값을 순서대로 추출한다. 따라서 원소의 삭제에 총 $O(\mathrm{log}n)$ 시간이 걸린다.
• 우선순위 큐를 이중연결리스트로 구현할 경우보다 시간적 장점 있다.

2) 힙 정렬

• 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입하는 데 $O(\mathrm{log}n)$ 시간이 걸린다.
• 삽입이 끝나면 힙이 빌 때까지 하나씩 삭제하는 데 $O(\mathrm{log}n)$ 시간이 걸린다. 원소들이 삭제된 순서가 원소들의 정렬 순서이다.
• 정렬 알고리즘의 복잡도는 $O(n\mathrm{log}n)$가 된다. 원소 하나에 대해 삽입과 삭제가 $\mathrm{log}n$이므로 n개 대해서는 $n*\mathrm{log}n$이기 때문이다.
• 이론적으로 임의의 데이터를 정렬하는데 $O(n\mathrm{log}n)$ 이하로 정렬하지는 못함이 증명되어 있으므로, 힙 정렬은 비교적 빠른 정렬 알고리즘이다.

아래는 힙 정렬의 예이다.

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

	# 원소를 삭제함. 즉, 가장 큰 값을 빼냄
    def remove(self):
    	# 맨 앞 요소는 None으로 비워두는 칸이므로 원소 개수는 2개 이상이어야 함
        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 = 2 * i  # 왼쪽 자식 인덱스
        right = 2 * i + 1  # 오른쪽 자식 인덱스
        smallest = i  # 가장 작은 값의 인덱스. 임시로 현재 노드값을 넣음

        # 왼 자식이 있고, 그 값이 더 클 때
        if left < len(self.data) and self.data[left] > self.data[smallest]:
            smallest = left  # 최대값의 인덱스 변경
        # 오른 자식이 있고, 그 값이 더 클 때
        if right < len(self.data) and self.data[right] > self.data[smallest]:
            smallest = right
            
		# 본인이 가장 큰 값이 아님
        if smallest != i:
            self.data[smallest], self.data[i] = self.data[i], self.data[smallest]
            	# 본인(i)과 가장 큰 값의 노드(smallest가 가리키고 있는 왼/오른쪽 노드) 자리 바꾸기
            self.maxHeapify(smallest)  # 재귀 호출로 그 아래 레벨로 넘어감