[TIL_2023.10.18] 자료구조와 알고리즘 (3) : 큐 Queues, 트리 Trees, 힙 Heaps

1주차 수요일, 3일차 Today I Learned

 

 

자료구조와 알고리즘 (3)
: 큐 Queues, 트리 Trees, 힙 Heaps

 

반응형

 

✏️ 학습 내용

1. 큐 (Queues)

"표를 사러 일렬로 늘어선 사람들로 이루어진 줄"이라는 의미로, 대기열이라고도 하며, 자료를 보관할 수 있는 (선형) 구조이다. 스택과는 반대로 선입선출 구조 (FIFO, First-In First-Out)를 갖는다. 즉, 데이터가 순서대로 쌓이며 가장 처음에 삽입된 자료가 가장 먼저 삭제된다.

큐의 핵심적인 두 가지 연산은 다음과 같다. 우선 데이터 원소를 큐에 넣는 동작을 인큐 (enqueue) 연산이라고 하고, 큐로부터 데이터 원소를 꺼내는 동작을 디큐 (dequeue) 연산이라고 한다.

 

 

큐의 동작

초기 상태는 비어 있는 큐 (empty queue)이다. Q.enqueue(Data) 형태를 통해서 데이터를 쌓을 수 있고, Q.dequeue() 형태를 통해서 맨 앞의 데이터를 꺼낼 수 있다.

 

https://roi-data.com/entry/자료구조-4-스택Stack이란-연산-구현방법

 

 

큐의 추상적 자료구조 구현

큐를 추상적 자료구조로 구현하고자 할 때는 대표적으로 두 가지 방법이 있다. (선형) 배열 구조를 이용하거나, 연결 리스트를 이용하는 방법이다. 이 외의 방법도 있지만 일단 이 두 가지만 먼저 살펴보기로 하자.

 

먼저, 이용하는 연산은 다음과 같다.

• size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함
• isEmpty() : 현재 큐이 비어 있는지를 판단 (size() == 0?)
• enqueue(x) : 데이터 원소 x 를 큐에 추가
• dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거 (또한, 반환)
• peek() : 큐의 맨 앞에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음

 

1) 배열 (Array)을 이용한 방법 : python 리스트와 메서드들을 이용

class AraayQueue : 
	
	def __init__(self) :  
    	# 빈 큐 초기화
		self.data = []   

	def size(self) :   
    	# 큐의 크기를 리턴
		return len(self.data)

	def isEmpty(self) :   
    	# 큐가 비어있는지 판단 (T/F)
		return self.size() == 0

	def inqueue(self, item) :   
    	# 데이터 원소 추가
		self.data.append(item)   

	def dequeue(self) :    
    	# 데이터 원소 삭제
		return self.data.pop(0)

	def peek(self) :   
    	# 큐의 맨 앞 원소 반환
		return self.data[0]

연산 복잡도는 전부 Q(1) 이고, dequeue의 경우엔 Q(n)이다. dequeue의 경우, 맨 앞의 원소를 꺼내면 그 뒤에 있던 원소들이 각각 한 칸씩 앞으로 움직이다가 맨 마지막은 비어있게 되는 연산이 실행되기 때문에 길이에 비례하는 연산이 걸리게 된다.

 

 

2) 연결 리스트를 이용한 방법 : 양방향 연결 리스트를 이용

class LinkedListQueue:

	def __init__(self):
		self.data = DoublyLinkedList()

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

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

	def inqueue(self, item):
		node = Node(item)
		self.data.insertAt(self.size() + 1, node)

	def dequeue(self):
		return self.data.popAt(self.size())

	def peek(self):
		return self.data.getAt(self.size()).data

 

이미 만들어진 파이썬 라이브러리를 이용해서 큐를 구현할 수도 있다.

from pythonds.basic.queue import Queue

 

 

원형 큐, 환형 큐 (Circular Queue)

 

기본 큐는 일렬로 늘어선 형태이다. 이 때에 deaueue()를 이용할 시에 길이에 따라 복잡도가 증가한다고 배웠다. (Q(n)) 이러한 단점을 보완하기 위해 환형 큐(원형 큐)를 이용할 수 있다.

환형 큐는 정해진 개수의 저장 공간을 빙 돌려가며 이용한다. 인덱스가 하나였던 큐에 비해 환형 큐는 두 개의 인덱스 변수가 존재한다. front 라는 데이터 꺼내는 곳, rear 라는 데이터 입력하는 곳 두 개이다.

 

# 선형 배열로 구현한 환형 큐
class CircularQueue :

	def __init__(self, n) :    # 빈 큐를 초기화, 인자로 주어진 최대 큐 길이 설정
    	self.maxCount = n 
        self.data = [None]*n   # 실제 데이터를 저장하려는 공간
        self.count = 0         # 현재 큐에 들어있는 데이터의 갯수
        self.front = -1 
        self.rear = -1
        
    def size(slef) :   # 현재 큐 길이 반환
    	return self.count == 0
    
    def isEmpty(self) : # 큐가 비어있는가?
    	return self.count == 0
        
    def isFull(self) :  # 큐가 꽉 차있는가?
    	return self.count == self.maxCount

	def endqueu(self, x) : 
    	if self.isFull() :
        	# IndexError('Queue full') exception 으로 처리
        self.rear = 
        self.data[self.rear] = x
        self.count += 1
        
	def dequeue(self) : 
    	if : 
        	raise IndexError('Queue empty')
        self.front = 
        x = 
        self.count -= 1
        return x
        
	def peek(self) : 
    	if :
        	raise IndexError('Queue empty')
		return

 

 

 

 

우선순위 큐 (Priority Queues)

우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 큐에서 원소를 꺼내는 원칙은 원소들 사이의 우선순위를 따른다.

 

우선순위 큐를 구현하기 위해 1) 큐에 원소를 넣을 때 우선순위 순서대로 정렬해두거나, 2) 큐에서 원소를 꺼낼 때 우선순위가 가장 높은 것을 선택하는 방법으로 접근할 수 있다. 1)의 방법이 더 유리하다.

 

이전과 같이 배열 및 연결 리스트로 구현할 수 있는데, 배열의 경우 공간적으로 좀 더 유리하고, 연결 리스트의 경우 시간적으로 좀 더 유리하다. 여기서 시간적으로 유리한 연결 리스트를 선택하면 좋다. 연결 리스트를 통한 우선순위 큐의 구현 코드는 아래와 같다. 주의할 점은 양방향 연결 리스트의 getAt() 메서드는 이용하지 않고, curr가 하나하나 이동하게 해야 한다. getAt() 메서드를 이용하면 어떤 포지션이 주어졌을 때, 반복문이 실행되는 동안 매번 그 포지션까지 칸을 세어가면서 진행을 하게 되기 때문이다.

 

from doublylinkedlist import Node, DoublyLinkedList

class PrioityQueue :
	
    def __init__(self, x) :   # 빈 큐 초기화
    	self.queue = DoublyLinkedList()
    
    def enqueue(self, x) :
    	newNode = Node(x)
        curr = 
        while and :   # 끝을 만나지 않을 조건, 우선순위 조건
        	curr = curr.next
        slef.queue.(curr, newNode)   # InsertBefore? After?

 

 

배열이나 연결 리스트로 구현한 우선순위 큐의 원소를 넣는 (enqueue) 연산의 복잡도는 O(n)으로서 큐의 길이에 비례하고, 원소를 꺼내는 (dequeue) 연산의 복잡도는 O(1)로 상수 시간, 즉 데이터 원소의 개수에 무관한 시간이 걸린다.

 

우선순위 큐는 배열이나 연결 리스트로 구현하지 않고, 힙(Heeps)으로 구현한다. 만약 ➀ 배열로 구현할 경우, 우선순위가 중간인 원소를 추가하는 과정에서 뒤의 데이터까지 인덱스를 모두 한 칸씩 뒤로 밀어야 한다는 단점이 있다. 시간 복잡도가 증가하게 되는 것이다. 최악의 경우 삽입해야 하는 위치를 찾기 위해 모든 인덱스를 탐색해야 할 수도 있고, enqueue의 복잡도가 O(n)이 된다. 그리고 ➁ 연결 리스트로 구현할 경우에도 배열과 마찬가지이다.

 

반면 ➂ 힙으로 구현할 경우, 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 반복된다. 힙으로 구현 시 시간 복잡도는 삭제는 O(log2n), 추가는 O(log2n)이다. 배열이나 연결 리스트가 삭제의 복잡도는 우위에 있어도, 추가의 복잡도가 힙으로 구현하는 것이 월등히 좋기 때문에 이처럼 힙으로 구현한다.

 

 

 

힙에 관한 자세한 설명은 아래 글을 참고하자!(힙 링크)

 

 

---

 

2. 트리 (Trees)

"나무"라는 뜻이며, 데이터의 배치 형태를 추상화한 2차원 자료 구조이고, 데이터 검색과 탐색에 널리 이용된다. 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프, 즉 순환하는 길이 없는 그래프이다.

 

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

 

트리의 특징 :

- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

 

 

트리의 용어 :

루트 (root) 노드 : 부모가 없는 노드, 맨 위의 노드로, 단 하나만 존재
리프 (leaf) 노드 : 자식이 없는 노드 (= 말단 노드, 잎 노드)
내부 (internal) 노드 : root나 leaf가 아닌 노드
간선 (edge) : 노드를 연결하는 선 (= link, branch)

 

형제 (sibling) : 같은 부모를 가지는 노드
부모 (parant) 의 부모~ : 조상 (ancestor)
자식 (child) 의 자식~ : 후손 (descendant)

노드의 크기 (size) : 자신을 포함한 모든 자손 노드의 개수
노드의 깊이 (depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨 (level) : 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수 (degree) : 하위 트리 개수 = 간선 수 (degree) : 각 노드가 지닌 가지의 수
트리의 차수 (degree of tree) : 트리의 최대 차수
트리의 높이 (height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

 

---

 

 

이진 트리 (Binary Tree)

모든 노드의 차수가 2 이하인 트리를 말한다. 이진 트리는 재귀적으로 정의할 수 있는데, 그 조건은 1) 빈 트리 (Empty tree)이거나, 2) 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리인데, 왼쪽과 오른쪽 서브트리가 모두 이진 트리인 경우이다.

 

https://velog.io/@dlgosla/CS-자료구조-이진-트리-Binary-Tree-vzdhb2sp#2-이진-탐색-트리binary-search-tree-bst

 

이진 트리의 추상적 자료구조를 위해 사용되는 연산은 현재 트리에 포함되어 있는 노드의 수를 구하는 size(), 현재 트리의 깊이(또는 높이; height)를 구하는 depth(), 그리고 순회 (traversal)가 있다. 추상적 자료구조를 구현하기 위해서, 먼저 노드에 data, left child, right child를 초기화하고, 트리에 root 를 초기화한다. size()와 depth()는 재귀적인 방법으로 쉽게 구할 수 있다.

 

먼저 각각 노드와 트리의 초기화는 다음과 같이 입력한다. 노드에 data, left child, right child를 초기화하고, 트리에 root 를 초기화했다.

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

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

 

그리고 size()는 재귀적인 방법으로 푼다. 노드에서 왼쪽과 오른쪽 각각 자식 노드에 값이 있으면 해당 사이즈를 재귀적으로 호출하여 값을 저장하고, 없다면 0을 저장한다. 최종적으로 왼쪽 자식 노드의 갯수, 오른쪽 자식 노드의 갯수, 그리고 자기 자신 하나를 더하여 그 값을 리턴한다. 그럼 노드의 사이즈를 알 수 있다. 트리는 루트가 존재할 경우, 이 사이즈를 재귀적으로 리턴한다.

class Node :
	def size(self) :
    	l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1   # 자기 자신 하나도 더해야 한다.

class BinaryTree : 
	def size(self) :
    	if self.root : 
        	return self.root.size()
        else : 
        	return 0

 

depth()를 구하는 알고리즘도 재귀적인 방법으로 쉽게 구할 수 있다. 왼쪽 서브트리의 depth와 오른쪽 서브트리의 depth 중에 더 긴 것을 구하고, 거기에 자기 자신 1을 더하면 구할 수 있다.

class Node :
	def depth(self) : 
		
        
class BinaryTree : 
	def depth(self) :

 

 

 순회 는 길이(깊이) 우선 순회 (DFS,

Depth first traversal)와 넓이 우선 순회 (BFS, Breadth first traversal)로 구분 된다. 그리고 DFS는 중위, 전위, 후위 순회로 나뉘어 진다.

 

중위 순회 in-order traversal : 왼쪽 서브트리 (하위) → 자기 자신 → 오른쪽 서브트리 순서로 순회한다.

전위 순회 pre-order traversal : 자기 자신 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 순회한다.

후위 순회 post-order traversal : 왼쪽 서브트리 (하위) → 오른쪽 서브트리 → 자기 자신 순서로 순회한다.

 

넓이 우선 순회 (BFS)는 재귀적으로 자연스럽게 구현되지 않는다. 즉, 이 알고리즘은 재귀적인 성질을 갖지 않는다. 대신 큐를 이용한 설계가 적합하다. 수준(level)이 낮은 노드 우선 방문하고, 같은 수준의 노드들 사이에는 부모 노드의 방문 순서에 따라 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 방문한다.

 

BFS 구현 알고리즘은 다음과 같이 설계할 수 있다. 우선 ➀ traversal에 빈 리스트, q에 빈 큐 를 초기화한다. ➁ empty tree가 아니라면,

root node를 q에 enqueue (추가)한다. ➂ 

q가 비어있지 않는 동안, q에서 dequeue (추출)한 원소를 node에 저장하고, node 방문 처리 (traversal.append)를 하며, node의 왼쪽과 오른쪽 자식 노드가 있으면 q에 추가한다. ➃ q == empty 라면, 모든 노드 방문이 완료된 것이므로, traversal을 리턴한다.

1. traversal에 빈 리스트, q에 빈 큐 `초기화`
2. root node를 q에 enqueue (추가)
3. q가 비어있지 않는 동안
   ➀ q에서 dequeue (추출)한 원소를 node에 저장
   ➁ node 방문 처리 (traversal.append)
   ➂ node의 왼쪽, 오른쪽 자식 노드가 있으면 q에 추가
4. q == empty 시 return traversal

 

# 넓이 우선 순회 BTS 구현 알고리즘
class Binary Tree : 
	def bft(self) :

 

 

---

 

 

이진 탐색 트리(Binary Search Tree, BST)

BST는 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진 트리이다. 모든 원소는 유일한 키를 갖고, 데이터 탐색 시에 유용하다.

 

https://velog.io/@dlgosla/CS-자료구조-이진-트리-Binary-Tree-vzdhb2sp#2-이진-탐색-트리binary-search-tree-bst

 

왼쪽은 작고, 오른쪽은 크고, 데이터를 탐색하는 방법이 배열 이진 탐색과 유사하다는 것을 알 수 있다. 정렬된 배열을 이용한 이진 탐색과 비교하여, 이진 탐색 트리의 장점은 데이터 원소의 추가, 삭제가 용이하다는 것이고, 단점은 공간 소요가 크다는 점이다. 이진 탐색 트리는 항상 O(logn)의 탐색 복잡도를 갖지는 않는다.

 

이진 탐색 트리의 데이터 표현은 각 노드는 (key, value) 쌍으로 한다. 키를 통해서 데이터 탐색이 가능해진다.
- insert(key, value) : 트리에 주어진 데이터 원소를 추가
- remove(key) : 특정 원소를 트리로부터 삭제
- lookup(key) : 특정 원소를 검색 (탐색)
- inorder() : 키의 순서대로 데이터 원소들을 나열
- min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색

 

추상적 자료 구조 알고리즘은 다음과 같이 구현할 수 있다. 먼저 노드와 트리를 초기화한다.

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

class BinSearchTree :
	def __init__(self) :
    	self.root = None

 

키의 순서대로 데이터 원소들을 나열하는 inorder() 연산 알고리즘은 다음과 같다.

class Node :     
    def inorder(self) :
    	traversal = []
        if self.left :
        	traversal += self.left.inorder()
        traversal.append(self)
        if self.right : 
        	traversal += self.right.inorder
        return traversal
        
class BinSearchTree :
	def inorder(self) :
    	if self.root : 
        	return self.root.inorder()
        else : 
	        return []

 

min(), max()도 간단하다.

class BinSearchTree :

	def min(self) :
	    if self.left : 
    		return.self.root.min()
        else : 
        	return self
    
    def max(self) :
    	if self.right : 
        	return.self.root.max()
        else : 
        	return self

 

트리에 주어진 데이터 원소를 추가하는 insert()는 다음과 같다. 입력 인자에는 키와 데이터 원소를 입력하고, 아무것도 리턴하지 않는다.

class Node : 
    def insert(self, key, data) :
    	if key < self.key : 
        elif key > self.key : 
        else : 
        	raise KeyError('...')
            
class BinSearchTree :
    def insert(self, key, value) : 
    	if self.root : 
        	self.root.insert(key, data)
        else : 
        	self.root = Node(key, data)

 

(중요) 특정 원소를 탐색하는 lookup() 연산 알고리즘은 다음과 같다. 입력 인자에는 찾으려는 대상 키를 입력하고, 찾은 노드와 그것의 부모 노드를 리턴한다. 만약 각각 없으면 None을 리턴한다.

class Node : 
    def lookup(self, key, parant=None) : 
    	if key < self.key :
        	if self.left : 
            	return self.left.lookup(key, 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, parant

class BinSearchTree :
    def lookup(self, key) :
    	if self.root : 
        	return self.root.lookup(key)
        else : 
        	return None, None

 

remove()는 다소 복잡하다. 크게 살펴보면 우선 1) key를 이용해서 노드를 찾고, ➀ 해당 key의 node가 없으면 삭제할 것 없으므로 False, 
➁ 찾은 node 제거한 경우 True로 구현한다. 단, 이 때 트리 구조 정리를 위해서 찾은 node의 부모 node도 알아내야 한다. 그리고 2) 이진탐색트리 성질을 만족하도록 트리의 구조를 정리한다. ➀ leaf 노드 삭제의 경우, 해당 node 삭제 후 부모 node의 링크를 조정하면 된다. ➁ 자식이 하나인 노드 삭제의 경우, 해당 node 삭제 후 삭제되는 노드 자리에 그 자식을 대신 배치하고, 부모 node의 링크를 조정하면 된다. 단, 삭제되는 노드가 root일 경우, 새로 들어오는 자식이 새 root가 된다. ➂ 자식이 둘인 노드 삭제의 경우, 삭제되는 노드보다 바로 다음 (큰) 키를 가지는 노드와 그 부모 노드를 찾고, 삭제되는 노드 자리에 그 노드를 배치 후 대신 이 노드를 삭제한다. 단, 해당 노드가 마지막 노드라면 다르게 조정해야 한다.

remove()

 

 

그렇다면 모든 이진 탐색 트리가 효율적일까? 이진 탐색 트리가 한쪽으로 치우친 경우, 이진 탐색 트리의 장점을 발휘하지 못하고, 선형 탐색과 같은 효율을 갖게 된다. 왼쪽 서브트리만 있거나, 오른쪽 서브트리만 있으면 효율적이지 않다. 어느 정도 왼쪽 오른쪽이 균형이 있어야 한다.

 

이러한 단점을 해결하기 위한 보다 나은 성능을 보이는 이진 탐색 트리들이 있다. 높이의 균형을 유지함으로써 O(logn)의 탐색 복잡도를 보장할 수 있다. 하지만 그렇게 트리의 구조를 유지하려다 보면 기초 이진 트리에 비해 삽입, 삭제 연산이 보다 복잡하다. AVL tree, Red-black tree가 이에 해당된다.

 

 

 

---

3. 힙 (Heaps)

이진 트리의 한 종류로, 이진 힙이라고도 한다. 힙은 데이터 원소들의 순서를 교묘하게 표현한 트리이며, 데이터 정렬에 이용할 수 있다. 또한 힙은 최대 힙 (max heap)과 최소 힙 (min heap)이 있다. 이 두 가지는 데이터 원소의 순서 기준이 내림차순이냐 오름차순이냐에 달라지고 완전히 대칭이다.

- 힙 정렬 (heap sort) : 힙을 이용하여 데이터를 정렬하는 알고리즘

 

최대 힙은 3가지의 성질을 유지하고 있는 이진 트리이다. 루트 노드가 항상 최댓값을 가져야 하며, 완전 이진 트리이고, 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.

최대 힙 3가지 성질 : 
1. 루트 노드는 항상 최댓값이다.
2. 완전 이진 트리이다.
3. 최대 힙 내 서브트리 또한 최대 힙이다. (재귀적)

 

이진 탐색 트리와의 비교 : 
1. 원소들은 완전한 크기 순으로 정렬되어 있는가? 이진 탐색 트리는 정렬되어 있지만, 힙은 아니다.
2. 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? 이진 탐색 트리는 빠르게 검색할 수 있지만, 힙은 아니다.
3. 부가의 제약 조건은 어떤 것인가? 힙의 3가지 성질이 있다.

 

 

추상적 자료구조 : 

 

연산은 빈 최대 힙을 생성하는 __init__(), 새로운 원소를 삽입하는 insert(item), 최대 원소 (root node) 반환과 동시에 이 노드를 삭제하는 remove()가 있다.

 

배열을 이용한 이진 트리의 표현은 노드 번호 m을 기준으로, 왼쪽 자식은 2*m, 오른쪽 자식은 2*m+1, 부모 노드는 m//2 형태로 하고, 완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서만 가능하다는 것을 이용한다.

 

 

초기화 설정 : 

 

class MaxHeap : 
	def __init__(self) : 
    	self.data = [None]   # 0번 인덱스는 버리기로 함 (root node의 index : 1)

 

원소 삽입 : 

최대 힙에 원소를 삽입하기 위해서, 1) 트리의 마지막 자리에 새로운 원소를 임시로 저장하고, 2) 부모 노드와 키 값을 비교하여 계속해서 위로 이동시킨다. 이 때 원소의 개수가 n인 최대 힙에 새로운 원소를 삽입하는 것의 복잡도는 부모 노드와의 대소 비교 최대 회수 O(log₂n) 이다. 즉, 최악복잡도 O(logn)의 삽입 연산이다. 부가의 제약 조건(완전 이진 트리여야 한다!)에 의해 n개의 노드로 이루어진 최대 힙의 높이(깊이)는 log(n) + 1로 정해진다다. 이 성질 때문에 데이터 원소의 삽입/삭제 연산의 실행 시간은 언제나 log(n) 에 비례한다는 것이 최대 힙의 장점이다.

 

파이썬에서 두 변수의 값을 바꾸면 insert()를 쉽게 구현할 수 있다.

class MaxHeap : 
	def insert(self, item) :

 

원소 삭제 : 

최대 힙에서 원소를 삭제할 때, 1) 최대 힙의 최댓값은 루트 노드에 있다. 이 루트 노드를 제거하면 된다. 하지만 루트 노드를 빼내면 완전 이진 트리를 만족하지 않으므로, 2) 트리 마지막 자리 노드를 임시로 루트 노드 자리에 배치해야 한다. 그 후 3) 자식 노드들과의 값을 비교하여 계속해서 아래로 이동한다. 자식이 둘 있을 수도 있다면 둘 중에 더 큰 값을 기준으로 이동하면 된다.

 

원소의 개수가 n인 최대 힙에서 최대 원소를 삭제하는 복잡도는 자식 노드들과의 대소 비교 최대 회수인 2 * log₂n이 된다. 최악 복잡도는 O(logn)이다. (n이 아무리 커져도 로그에 비례하는 연산이다.)

class MaxHeap :
    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)   # max heap 구조 유지하기 위함
		else :  
        	data = None
        return data

먼저 루트 노드 self.data[1]와 마지막에 있는 노드 self.data[-1]의 값을 각각 뒤바꾼다. 그리고 맨 마지막으로 이동된 삭제하고자 한 루트 노드를 pop으로 삭제하면 된다.

 

여기에서 maxHeapify가 나오는데, 힙을 완전 이진 트리 구조로 유지하기 위해서 필요한 작업들을 수행해야 한다. 자기 자신의 값을 받고, 왼쪽 자식과 오른쪽 자식을 구한다. 그 다음 자신 i, 왼쪽 자식 left, 오른쪽 자식 right 중 최대를 찾아 이 인덱스를 smallest에 담으면 된다. 그리고 만약 자신보다 큰 값을 가진 자식을 발견한 경우, 현재 노드 i와 최댓값 smallest의 값 바꿔야 한다. 최종적으로 자기 자신을 재귀적으로 호출하면 된다. 자기 자신이 최대 키를 가지는 경우 알고리즘은 종료 된다. 이 경우는 자식이 없게 되는 리프 노드가 될 경우도 포함되므로, 최대를 찾을 때 왼쪽 자식이 있는지 없는지도 고려해야 한다.

class MaxHeap : 
	def maxHeapify(self, i) : 
    	left = 
        rignt = 
        smallest = o
        # 자신 i, 왼쪽 자식 left, 오른쪽 자식 right 중 최대를 찾아 이 인덱스를 smallest에 담기
        if smallest != i :   # 큰 값을 가진 자식을 발견한 경우
        	# 현재 노드 i와 최댓값 smallest의 값 바꾸기
            # 재귀적으로 호출

 

 

 

 

최대/최소 힙의 응용은 우선 순위 큐를 구현할 때, 주어진 데이터를 정렬(힙 정렬)할 때 이용할 수 있다.

 

우선 순위 큐를 만드려면, enqueue 할 때 "느슨한 정렬"을 이루고 있도록 해야 한다. 즉, enqueue 되는 원소들을 최대/최소 힙에 삽입하면 이미 느슨한 정렬을 이루고 있어서 나중에 dequeue 할 때에 순서대로 우선순위에 따르게 할 수 있다. 이 구조를 유지하기 위해 O(logn)의 복잡도(최대/최소 힙 삽입의 복잡도)를 갖는 연산이 수반된다. dequeue를 할 때는 최댓값을 순서대로 추출하는데, 이 역시도 O(logn)의 복잡도를 갖는다. 이것을 양방향 연결 리스트 이용 구현과 효율성을 비교해 볼 수 있다. 힙의 응용이 시간적으로는 장점이 있을 것이다.

 

힙 정렬은 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입하면 된다. 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제하면 된다. 원소들이 삭제된 순서가 결국 원소들의 정렬 순서가 된다. 각각 삽입하고 삭제하는 연산의 복잡도는 O(logn)이지만, 정렬 알고리즘 자체의 복잡도는 O(nlogn)가 된다.

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

 

 

---

 

☁️ 소감

분량이 너무 많다. 10개의 강의를 듣고 이해하는 데에만 거의 6시간 가량 걸렸다. 실습 문제는 시간이 없을 것 같아서 건너 뛰었는데, 다시 작성한 내용들을 한 번씩 살펴보고 공부하면서 실습을 풀어야겠다. 점점 몰라서 검색해보느라 틀어 놓은 웹사이트들이 늘어나고 있다.

 

사실 방대한 범위, 중요한 내용을 담고 있는 자료구조와 알고리즘을 공부하는 데에 일주일이 충분하지 않다. 그러므로 조급하지 않기로 했다. 초보자답게 차근차근 해나가자!

 

그리고 지금 수강하는 내용이 프로그래머스에서 제공하고 있는 "어서와! 자료구조와 알고리즘은 처음이지?" 강의와 동일한 것을 알게 되었다. 다른 블로그에 이를 기반으로 수강한 사람들이 정리한 내용도 많아서 찾아볼 자료는 넘쳐나는 것 같다.