[ 자료구조 ] 자료구조 이론 정리(2)

I . Deque(데크)

1. Deque의 개념과 구조

deque 는 Double-Ended-Queue의 줄임말로, 양방향에서 데이터를 처리할 수 있는 Queue형 자료구조이다.

2. Deque의 메서드 정리

from collections import deque

deq = deque(['a','b','c'])
arr = ['1','2','3']

deq.append('d') # deque(['a', 'b', 'c', 'd'])
deq.appendleft('e') # deque(['e', 'a', 'b', 'c', 'd'])
deq.pop() # deque(['e', 'a', 'b', 'c'])
deq.popleft() # deque(['a', 'b', 'c'])
deq.extend(arr) # deque(['a', 'b', 'c', '1', '2', '3'])
deq.extendleft(arr) # deque(['3', '2', '1', 'a', 'b', 'c', '1', '2', '3'])
deq.rotate(1) # deque(['3', '3', '2', '1', 'a', 'b', 'c', '1', '2'])
deq.rotate(-1) # deque(['3', '2', '1', 'a', 'b', 'c', '1', '2', '3'])

 

deque.append(x) : x를 데크의 오른쪽 끝에 삽입한다
deque.appendleft(x) : x를 데크의 왼쪽 끝에 삽입한다
deque.pop() : 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서는 삭제한다
deque.popleft() : 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서는 삭제한다
deque.extend(array) : 배열 array를 순환하면서 데크의 오른쪽에 추가한다
deque.extendleft(array) : 배열 array를 순환하면서 데크의 왼쪽에 추가한다
deque.remove(x) : x를 데크에서 찾아 삭제한다
deque.rotate(num) : 데크를 num만큼 회전한다 (양수면 오른쪽, 음수는 왼쪽으로)

 

II. Heap(힙)

1. 힙의 개념 및 정리

• 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조
• 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조
• 반정렬 상태를 유지
  ex. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큼 / 작음
• 이진탐색트리(BST)와 달리 중복된 값이 허용된다.

2. 힙의 데이터 삽입/삭제

A) 들어올 새 노드를 우선순위가 가장 낮다는 가정을 하고 맨 끝 위치에 저장
B) 부모 노드와 우선 순위를 비교해서 위치가 바뀌어야 하면 바꾼다.
C) 올바르게 위치할 때까지 B 반복

3. 힙의 표현

• 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
• 부모의 인덱스 = (자식의 인덱스) / 2

4. 힙 : 파이썬에서의 구현

import heapq

hq = []

heapq.heappush(hq, 4)
heapq.heappush(hq, 1)
heapq.heappush(hq, 3)
heapq.heappush(hq, 7)

heapq.heappop(hq) # 1

x = [4, 3, 1, 2, 5, 6]
print(x) # [4, 3, 1, 2, 5, 6]
heapq.heapify(x)
print(x) # [1, 2, 4, 3, 5, 6]