0%

파이썬 자료구조와 알고리즘 - 추상 데이터 타입(우선순위 큐, 연결 리스트)

작성일 In Disqus:

이번 포스트에서는 우선순위 큐, 연결 리스트에 대해 정리할 것이다.

우선순위 큐와 힙

  • 우선순위 큐는 항목마다 우선순위가 있고, 우선순위가 같으면 큐의 순서를 따른다
  • 우선순위 큐는 주로 힙을 사용해 구현한다.

힙

img

  • 힙은 각 노드가 하위 노드보다 작은 or 큰 이진 트리이다.

리스트에서 가장 작은(또는 큰) 값에 반복적으로 접근해햐 한다면 힙이 유용하다.

최대 힙, 최소 힙에서 각각 최댓값, 최솟값은 루트 노드에 위치하고 있으니, 이 요소를 처리하는 시간복잡도는 O(1)이다.

조회, 추가, 수정을 처리하는 시간복잡도는 O(logn)이다.

heapq 모듈

파이썬에는 힙 자료구조를 사용할 수 있는 heapq 모듈이 존재한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapq

h = []
# 아이템 추가
heapq.heappush(h, (5,'55'))
heapq.heappush(h, (6,'66'))
heapq.heappush(h, (1,'11'))

# 아이템 삭제
heapq.headpop(h)
Out : (1, '11')
heapq.headpop(h)
Out : (5, '55')
heapq.headpop(h)
Out : (6, '55')
  • 메서드
    • heapq.pushpop(heap, item) : 새 item을 힙에 추가한 후 가장 작은 항목을 제거하고 반환
    • heapq.merge(*iterables) : 여러개의 이터러블한 객체를 병합해 하나의 정렬된 이터레이터를 반환

Heap 구현

  • 파이썬 클래스를 이용해 리스트를 이용한 힙을 구현할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# Max_Heap 구현
class Heap:
    def __init__(self, data=None):
        self.data = data or []
        for i in range(len(self.data)//2, -1, -1):
            self._max_heap_check(i)
            
    def __repr__(self):
        return repr(self.data)
    
    def parent(self, i):
        if i == 0:
            return ('this node is root node')
        if i%2 == 0:
            return (i-2)//2
        else:
            return (i-1)//2
    
    def left_child(self, i):
        return i*2+1
    
    def right_child(self, i):
        return i*2+2
    
    def _max_heap_check(self, i):
        largest = i
        print("start!", largest)
        left = self.left_child(i)
        right = self.right_child(i)
        n = len(self.data)
        
        largest = (left < n and self.data[left] > self.data[i]) and left or i
        print(largest)
        largest = (right < n and self.data[right] > self.data[largest]) and right or largest
        print(largest)
        if i is not largest:
            self.data[i], self.data[largest] = self.data[largest], self.data[i]
            print("----", largest)
            self._max_heap_check(largest)
    
    def extract(self):
        max_value = self.data[0]
        self.data[0] = self.data[-1]
        del self.data[-1]
        self._max_heap_check(0)
        return max_value
    
    def insert(self, item):
        i = len(self.data)
        self.data.append(item)
        while (i != 0) and item > self.data[self.parent(i)]:
            print("!!!!!!", self.data)
            self.data[i] = self.data[self.parent(i)]
            i = self.parent(i)
        self.data[i] = item

연결 리스트

연결 리스트는 값과 다음 노드에 대한 포인터를 갖는 노드로 이루어진 리스트이다.

연결 리스트를 이용해 스택, 큐를 구현할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Node:
    def __init__(self, value=None, pointer=None):
        self.value = value
        self.pointer = pointer
    
    def getData(self):
        return self.value
    
    def getNext(self):
        return self.pointer
    
    def setData(self, newData):
        self.value = newData
    
    def setNext(self, newpointer):
        self.pointer = newpointer
        

# Node 클래스를 이용한 연결 리스트
a = Node("a")   
b = Node("b", a)
b.getNext().getData()
Out : 'a'