반응형 힙2 C# 힙 트리(Heap tree) 구현 힙 트리(Heap tree) 구현완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 힙 트리(Heap)의 종류최대 힙(max heap)부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리key(부모 노드) >= key(자식 노드)최소 힘(min heap)부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리key(부모 노드) >= key(자식 노드) 힙 트리(Heap tree)의 구현힙을 저장하는 표준적인 자료구조는 배열이다.구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용하지 않는다.특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.힙에서의 부모 노드와 자식 노드.. 2024. 2. 5. 힙(Heap) vs 이진 탐색 트리(Binary Search Tree) 힙(Heap)이란?힙(Heap)은 완전 이진 트리(Complete Binary Tree)를 기반으로 하는 자료구조로서, 힙에 데이터를 저장해 놓으면 O(1), 즉 상수 시간에 최솟값이나 최댓값에 접근할 수 있다. 이것이 가능한 이유는 힙이 최솟값 또는 최댓값을 트리의 루트(root)에 저장해 놓기 때문이다. 보통, 최솟값을 트리의 루트에 위치시키는 힙을 최소 힙(Min Heap)이라고 하고, 최댓값을 트리의 루트에 위치시키는 힙을 최대 힙(Max Heap)이라고 한다. 힙에서 값을 연속해서 꺼내면 자동으로 정렬되는 효과가 나기 때문에 기본적으로 정렬에 활용할 수 있다. 몇 번째로 가장 작은 값 또는 가장 큰 값을 구해야 하는 상황에서도 유용하게 사용할 수 있다. 예를 들어, 3번째로 작은 값이 필요하다.. 2023. 10. 4. 이전 1 다음
