[힙] 16. 힙으로 구현한 우선순위 큐 평가

우선순위 큐를 구현할 때는 힙 말고도 다른 자료 구조들을 활용할 수도 있다. 예를 들어 정렬된 동적 배열 정렬된 더블리 링크드 리스트 으로도 우선순위 큐를 구현할 수 있는데, 이번에 이 방법들을 사용하는 것과 힙을 사용하는 걸 한번 비교해 보겠다. 정렬된 동적 배열 정렬된 동적 배열으로도 우선순위 큐를

[힙] 15. 힙 삽입, 추출 시간 복잡도

힙의 데이터 삽입 시간 복잡도 힙 안에 총 n 개의 Node 가 있다고 가정하고, 데이터 삽입의 3 단계를 보자. 힙의 마지막 인덱스에 Node 를 삽입한다. 삽입한 Node 와 그 부모 Node 르르 보교해서 부모 Node 가 더 작으면 둘의 위치를 바꾼다. 삽입한 Node 와 그 부모 Node

[힙] 14. 힙 우선순위 데이터 추출 구현

실습과제 데이터 추출의 과정을 정리해보면 아래의 4단계로 정리할 수 있다. root Node와 마지막 Node의 위치를 바꾼다. 마지막 위치로 간 원래 root Node의 데이터를 별도 변수에 저장하고, Node는 힙에서 지운다. 새로운 root Node를 대상으로 heapify해서 망가진 힙 속성을 복원한다. 2단계에서 따로 저장해 둔 최우선순위 데이터를 리턴한다. 이 기능을 PriorityQueue

[힙] 13. 힙에서 최고 우선순위 데이터 추출하기

힙에서 root Node 데이터 추출하기 힙에서 우선순위가 가장 높은 데이터를 추출하고 싶다. 우선순위의 기준은 우리가 정하기 나름아다. 여기서 가장 큰 데이터가 높은 우선순위를 갖는다고 가정하자. 그러면 힙에서 가장 큰 데이터를 추출하고 싶은 것이다. root Node 에 가장 큰 데이터 17 이 있는데,

[힙] 12. 힙 데이터 삽입 구현하기

실습과제 먼저 우선순위 큐를 PriorityQueue라는 클래스로 정의하고 그 안에 힙을 두겠다. PriorityQueue 클래스에는 heap이라는 인스턴스 변수가 있고, 그것은 파이썬의 리스트를 가리킨다. 가장 처음 heap에는 None이라는 원소 하나만 있는데, 이제 이 힙에 데이터를 하나씩 삽입하려고 한다. 힙에 데이터를 삽입하는 메소드의 이름은 insert 이다. insert 메소드는 데이터를 삽입할 때 리스트가 계속 힙의

[힙] 11. 힙에 데이터 삽입하기

힙으로 우선순위 큐를 구현하기 위해서는 힙에 데이터를 삽입하고, 또 삭제하는 방법을 알아야 한다. 아래의 사진에서 데이터 15 를 삽입하고 싶다고 하자. 그러면 힙의 가장 마지막 인덱스에 15 를 삽입해 준다. 15 는 지금 힙 속성을 어기고 있다. 15

[힙] 10. 우선순위 큐

힙을 사용하는 대표적으로 2가지 목적 1. 정렬 2. 우선순위 큐라는 추상 자료형을 구현하기 위함 우선순위 큐 우선순위 큐는 큐나 스택처럼 추상 자료형이다. 우선순위 큐는 큐랑 굉장히 비슷하다. 그런데 큐는 먼저 들어간 데이터가 먼저 나오는 자료형이다. 우선순위 큐는 각 데이터에는 우선순위가 있고 그 우선순위가 높은 데이터가 먼저

[힙] 9. 힙 정렬 시간 복잡도 + 평가

힙 정렬 시간 복잡도 힙 정렬이 얼마나 효율적인 정렬 방법인지 알아보자. 힙 안에 있는 Node 의 개수를 n 이라고 했을 때, 힙 정렬의 시간 복잡도는 어떻게 될까? 힙 정렬의 각 단계를 보면서 생각해보자. 힙 정렬의 각 단계는 아래와 같다. 리스트를 힙으로 만든다. root Node 와 마지막 Node

[힙] 8. 힙 정렬 구현하기

실습과제 힙 정렬을 직접 구현해보자. 어떤 리스트 하나가 있다고 하자. 이때 그 리스트를 힙 정렬하려면 먼저 리스트를 힙으로 만든다. root Node와 마지막 Node의 위치를 바꾼다. 마지막 위치로 간 기존의 root Node는 이제 힙에서 없다고 가정한다. 새로운 root Node가 힙 속성을 지킬 수 있게 heapify 한다. 힙에 남아있는 Node가 없도록

[힙] 7. 힙 정렬

힙 정렬 힙을 이용한 정렬 알고리즘 아래 사진과 같은 힙이 있다고 가정하자. 힙 속성 때문에 root Node 에 있는 14 가 힙에서 가장 큰 데이터다. 여기서 root Node 와 마지막 Node 의 위치를 바꾼다. 그럼 3 이 root 로 올라가니까 힙 속성이