Computer Science & Engineering Basic Knowledge Test : Heap / Stack / Queue / Deque
Heap, Stack 그리고 Queue 알고리즘 정리를 위한 포스팅
Heap
힙 자료구조는 완전 이진 트리의 일종으로 우선순위 큐를 구현하기 위해 사용하는 자료구조이자 여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
우선순위 큐를 구현할 때는 내부적으로 최소 힙 혹은 최대 힙을 이용
최소 힙(Min Heap)
값이 낮은 데이터가 먼저 삭제
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
파이썬 라이브러리에서는 기본적으로 최소 힙 구조를 이용
다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하기 때문에 최소 힙 구조 기반 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적합
최소 힙을 최대 힙처럼 사용하려면?
일부로 우선순위에 해당하는 값에 음수 부호()를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호()를 붙여서 원래의 값으로 돌리는 방식 사용 가능
최대 힙(Max Heap)
값이 큰 데이터가 먼저 삭제
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
Heap의 구현
Heap을 저장하는 표준적인 자료구조는 배열
-
배열의 첫 번째 인덱스인 0은 사용되지 않는다.
-
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
-
힙에서의 부모 노드와 자식 노드의 관계
왼쪽 자식의 인덱스 = 부모의 인덱스 * 2
오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1
부모 인덱스 = 자식의 인덱스 / 2
Heap의 삽입
heap = [0,2,3,5,4,7,6]
def Insert(num) :
# 1. 제일 마지막 단말 노드에 데이터를 삽입한다.
heap.append(num)
numIdx = len(heap)-1
# 2. 부모 노드랑 계속 비교하면서 부모 노드가 자신보다 크다면 부모와 자신의 위치를 swap
# 3. 2번 조건을 만족하지 않을 때까지 또는 자신이 루트 노드가 아닐 때까지 반복한다.
while ((numIdx != 1) and (num < heap[numIdx//2])) :
heap[numIdx], heap[numIdx//2] = heap[numIdx//2], heap[numIdx]
numIdx = numIdx // 2
print(heap)
Insert(1)
# 출력 결과
[0, 2, 3, 1, 4, 7, 6, 5]
[0, 1, 3, 2, 4, 7, 6, 5]Heap의 삭제
heap = [0, 1, 3, 2, 4, 7, 6, 5]
def Delete(heap) :
# 1. 가져올 '최소값'을 미리 저장해준다.
result = heap[1]
# 2. 가장 마지막 노드의 값과 루트 노드의 값을 Swap 해준다.
heap[-1], heap[1] = heap[1], heap[-1]
# 삭제할 값을 맨 뒤로 보냈으니, 삭제해준다.
heap.pop()
# 3. 현재 노드에서 자식 노드와 비교 하면서 자식 노드가 더 작은 값이라면 Swap해준다.
# 4. 위치를 찾을 때 까지 3번 과정을 반복한다.
parent = 1
while (True) :
child = parent * 2
if (child+1 < len(heap) and heap[child] > heap[child+1]) : child += 1
if (child >= len(heap) or heap[child] > heap[parent]) : break
heap[child], heap[parent] = heap[parent], heap[child]
parent = child
print(result,heap)
Delete(heap)Heap이 빠른 이유
단순한 순차 탐색으로 최댓값, 최솟값을 찾을 경우 O(N)의 탐색 시간이 소요
하지만, 힙의 경우 O(logN), 즉 트리의 높이만큼만 비교를 하게되기 때문에 순차 탐색보다 빠른 것!
Stack
가장 나중에 삽입된 데이터를 가장 먼저 삭제 : 후입선출(LIFO, Last-In-First-Out) 구조
스택에서 top을 통해 삽입하는 연산을 'push', top을 통한 삭제하는 연산을 'pop'이라고 함
Queue
가장 먼저 삽입된 데이터를 가장 먼저 삭제 : 선입선출(FIFO, First in first out) 방식
- 삽입연산 : enQueue
- 삭제연산 : dnQueue
Priority Queue
우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징
Python에서 우선순위 큐가 필요할 때 :
PriorityQueue 혹은 heapq를 사용할 수 있으며 둘 다 우선순위 큐 기능을 지원함
다만, heapq가 일반적으로 더 빠르게 동작하기 때문에 heapq를 사용하는 것을 권장함
Deque
Double-ended Queue의 약자
(2022-10-06 수정)
그렇다면 덱(Deque)이란?
양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조
큐와 스택을 합친 형태로 생각할 수 있다.
22-02 코테스터디 3주차 큐, 스택 풀면서 추가 문제 정리 예정[Reference]
이것이 취업을 위한 코딩테스트다
[자료구조 힙] 최소힙, 최대힙
/LGTM bb