muntari Log muntari Log

힙을 활용하는 대표적인 2가지 방법 1. 정렬 2. 우선순위 큐를 구현하는 법 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 많이 사용된다! 정렬 알고리즘 데이터를 재배치하는 구체적인 방법을 정렬 알고리즘이라 한다. 삽입 정렬, 선택 정렬, 퀵 정렬, 합병 정렬 + 힙 정렬 등이 있다. 보통 정렬 알고리즘의 경우 O(n logn) 정도만 되도 효율이 좋은 측에 속한다 하니 아래의 시간 복잡도를 서로 비교해보자. 힙 정렬 Tree = [None, 14, 8, 12, 5, 4, 10, 6, 2, 1, 3] 위 예시로 힙 정렬 알고리즘의 방법은 아래와 같이 정리 할 수 있다. 1. 힙을 만든다. (이때 최댓값을 구하고 싶으면 max heap을 반대의 경우 min ..

힙 완전 이진 트리를 기 이진 트리를 기본으로 하는 자료구조로 트리의 일종이며 아래 두개의 조건을 만족하는 트리이다. 최댓값 , 최솟값을 쉽게 추출 할 수 있는 자료구조이다. 이러한 힙은 힙_2에서 설명할 우선순위 큐를 위하여 만들어진 자료구조라 한다. 1. 형태 속성 : 힙은 완전 이진 트리여야 한다. 2. 힙 속성 : 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 작아야 한다. - Heap은 부모 노드가 항상 자식 노드보다 크거나 같아야 하는 경우(max heap)와 부모 노드가 항상 자식 노드보다 작거나 같아야 하는 경우(min heap)로 나눌 수 있다. 최댓값을 추출하고자 할때는 부모 노드가 자식 노드보다 항상 큰 max heap으로 최솟값을 추출하고자 할때는 부모 노드가 자식 노드보다 ..