목록힙 (1)

codinging

[자료구조] 우선순위 큐(Priority Queue) 와 힙(Heap) 알아보기

우선순위 큐 우선순위 속성을 가지는 큐 우선순위 큐는 배열, 연결 리스트, 힙으로 구현 할 수 있다. 힙 구현 방식이 시간 복잡도가 가장 낮기 때문에 힙으로 구현한다.(O(logN)) 힙 힙 순서 속성을 가지는 완전 이진 트리(자유 저장소 힙이 아님) 힙의 삽입 연산 🐬 1 : 힙의 최고 깊이 가장 우측에 새 노드 추가.(완전 이진 트리 유지) 🐬 2 : 삽입한 노드를 부모 노드와 비교한다. 삽입한 노드가 부모 노드보다 크면 맞는 위치니 연산 종료. 🐬 3 : 삽입한 노드가 부모 노드보다 작으면 부모 노드와 삽입한 노드의 위치를 교환. 교환 후 2번 - 3번 반복 예시 다음 힙에 값이 7인 노드를 삽입하는 예시다. 값이 7인 노드를 힙의 마지막에 추가하고 부모 노드와 비교한다. 7은 31보다 작으므로 이..
Data Structure 2023. 4. 2. 13:34
이전 Prev 1 Next 다음