728x90 반응형 heap2 [자료 구조] 힙(Heaps) 힙(Heaps) 구조란? 👉 힙은 트리처럼 생긴 데이터 구조이다. 다른 트리형 데이터 구조와는 달리 자식을 가리키는 포인터 대신 데이터를 배열에다 저장한다. 따라서 인덱스를 활용하여 자식 노드에 간단히 접근할 수 있다. 👉 바이너리 힙(Binary Heap)의 경우 배열의 첫 번째 요소를 root로 삼고 좌우 자식 노드들이 번갈아가며 배열에 들어간다. 👉 부모 노드의 값이 자식 노드의 값보다 크면 최대 힙(Max-Heap), 작으면 최소 힙(Min-Heap)이라고 한다. 🔴 [2, 4, 23, 12, 13]과 같은 배열로 된 힙 구조를 그림으로 나타내면 다음과 같다. 힙 인덱스 🔴 바이너리 힙 구조에서 각 노드에 접근하기 위해 활용하는 인덱스는 다음과 같다. 퍼컬레이션(Percolation): Bubbl.. 2022. 11. 30. 힙 정렬(Heaps sort)에 대해 알아보자! 힙(Heaps)이란 무엇인가? 힙이란 트리(tree)처럼 생긴 데이터 구조이다. 부모가 자식보다 커서 내림차순 구조인 것을 max-heap, 부모가 자식보다 작아서 오름차순인 구조를 min-heap이라 한다. 데이터를 정렬하는 데 유용하게 쓰인다. 다른 트리 데이터 구조와 달리 자식에 대한 포인터를 가지지 않고 데이터를 저장하는 데 배열을 활용한다. 이번 글에서는 바이너리 힙(binary heaps)만을 다루겠다. 힙 구조 min-heap 구조를 그림으로 나타내면 다음과 같다. 위와 같은 min-heap은 뿌리 노드(root node)가 가장 낮은 값이 되고, max-heap은 뿌리 노드가 가장 높은 값이 된다. 바이너리 힙(Binary Heap)의 배열 인덱스 구조 바이너리 힙에서 다음과 같은 배열 인.. 2022. 6. 23. 이전 1 다음 728x90 반응형
