힙1 [C++/자료구조] 힙(Heap) Heap : 힙 - 특징 1) 완전 이진 트리 형태 2) 부모 노드와 자식 노드 간의 대소관계가 정해진 완전 이진 트리 구조 3) 루트 노드는 항상 최솟값 또는 최대값을 가진다 4) 최소 힙 또는 최대 힙이 있다. - 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작은 경우 - 최대 힙 : 부모 노드의 값이 자식 노드의 값보다 큰 경우 - 장점 1) 최소값 또는 최대값을 상수시간 O(1)에 찾을 수있다. 2) 정렬, 우선순위 큐 등에서 유용하게 사용 3) 이진 탐색 트리보다 간단하고 빠르게 구현할 수 있다. - 단점 1) 중복된 값의 처리가 어렵다. 2) 삽입, 삭제, 연산에 시간 복잡도가 O(log n)이 소모된다. Heap.h #pragma once void DoHeap(); class Heap .. 2023. 7. 15. 이전 1 다음
