데이터구조 - (6) 우선순위 큐:힙

데이터 집합

- 정적 데이터 집합 : 한번 구축되고 나면 변하지 않음

​

- 동적 데이터 집합 : 데이터가 계속 변함

Dictionary(Table) : 삽입, 삭제, 검색을 지원하는 동적 데이터 집합 (배열, 리스트, 해시 테이블 등)

우선순위 큐 : 삽입, 최우선 원소 삭제, 최우선 원소 검색 지원하는 동적 데이터 집합(배열, 리스트 힙 등)

​

-> 테이블은 삭제할 원소를 제공하지만, 우선순위 큐는 가장 높은 우선순위를 가진 원소만 삭제 가능하다.

-> 삽입의 경우 둘 다 삽입할 원소를 제공한다, 또한 값의 중복은 우선순위 큐만 허용한다.

 

우선 순위 큐

배열 ,리스트, 연결리스트 등의 선형 자료구조로 구현 가능하지만, Heap으로 구현하는 것이 효율적이다.

우선순위 큐는 우선순위를 관리하기 위한 특수한 성질을 가진 자료구조이다.

​

출처 : 쉽게 배우는 자료구조 with 파이썬

힙을 이해하기 위해서는 이진 트리를 먼저 알아야 한다.

이진 트리는 루트를 기반으로 최대 2개까지 자식을 가지는 가지 치기 형식의 구조이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

여기서 포화 이진 트리는 모든 노드가 정확히 2개씩의 자식 노드를 가지도록 꽉 채워진 트리이다.

노드 수가 2^k-1개일 때만 가능하다.

출처 : 쉽게 배우는 자료구조 with 파이썬

완전 이진 트리는 만약 노드의 수가 맞지 않으면 맨 마지막 레벨은 왼쪽으로 채워나가는 형태이다.

힙을 구현할 때 필요한 조건 중 하나이다.

​

- 힙의 조건

1. 완전 이진 트리
2. 모든 노드는 값을 갖고, 자식 노드 값보다 크거나 같다.

​

+ 최대힙 : 루트가 최대값을 가짐

최소힙 : 루트가 최소값을 가짐

​

출처 : 쉽게 배우는 자료구조 with 파이썬

오른쪽의 경우 완전 이진 트리 구조를 만족하지 않기에 힙이 될 수 없다.

참고로 파이썬에서 힙을 구현할 때 배열로 구현한다.

배열은 그 자체로 완전 이진 트리로 볼 수 있다.

 

 

힙의 객체 구조

- 삽입

출처 : 쉽게 배우는 자료구조 with 파이썬

 

삽입을 진행하는 일부의 내용이다.

완전 이진 트리를 만족하게 값을 추가한 뒤에 최대힙을 만족하기 위해

부모 노드를 찾아가 추가한 값이 크면 부모 노드와 교환한다.

이 과정을 루트 혹은 변화가 없을 때까지 반복한다.

참고로 i의 부모 노드는 (i-1)/2로 찾을 수 있다.

​

파이썬으로는 아래와 같이 구현할 수 있다.

재귀 구조를 사용해 위의 내용을 그대로 구현한 것이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

​

- 삭제

출처 : 쉽게 배우는 자료구조 with 파이썬

맨 위의 값인 루트 값과 제일 마지막 값을 교환한 후 루트 값을 삭제한다.

이후 루트 값과 그 아래 자식 노드의 값을 비교하며 자식이 더 크면 교환하는 방식으로 진행한다.

참고로 2개의 자식 중 더 큰 값을 찾아 교환하며 내려간다.

파이썬으로 아래와 같이 구현할 수 있다. 삽입보다는 조금 더 복잡한 형태이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

출처 : 쉽게 배우는 자료구조 with 파이썬

​

- 힙 만들기

임의의 리스트가 주어지면 그 리스트를 힙으로 만드는 과정이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

맨 마지막 노드부터 시작한다. 해당 값과 그 부모의 값을 비교하여 더 크면 교환한다.

위의 형태는 A[3]부터 시작하여 A[2]->A[1]->A[0]까지 진행하며 힙 구조를 완성시킨다.

파이썬 코드로 구현하면 아래와 같다.

위에서 만들었던 코드를 사용하여 구현할 수 있다.

이는 맨 마지막 노드의 부모 노드부터 -1씩 감소하여 0까지 반복하는 for문이다.

직접 위의 예시에 적용해보며 이해하면 좋을 것 같다.

출처 : 쉽게 배우는 자료구조 with 파이썬

​

이들의 수행 시간을 정리하면

Heap의 크기가 n일 때 힙 만들기는 빅 세타n,

삽입과 삭제는 빅오log n의 시간이 걸린다.