jyoon dev log

힙 정렬 (Heap Sort) 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬 방식 힙 정렬은 병합 정렬과 퀵 정렬만큼 빠른 정렬 알고리즘이다. 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리다. 힙에는 최대 힙과 최소 힙이 존재하는데 최대 힙은 부모 노드가 자식 노드보다 큰 힙이라고 할 수 있다. 힙정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야 한다. 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘 (Heapify Algorithm)을 사용한다. 힙 생성 알고리즘은 특정한 하나의 노드에 대해서 수행하는 것이다. 힙 생성 알고리즘은 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 힙 정렬은 병합 정렬과 다..

힙이란? 최대값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조다 최소힙은 작은 값이 항상 가장 위에 노드에 있게해서 트리의 루트에는 가장 작은 값이 오게하는 최소힙이다. 가장 큰값이 맨 위에 오도록하는 구조가 최대힙이다. 최소힙에 노드 삽입하기 완전 트리에 맨 끝에 노드를 추가한다. 트리가 컴플리트 바이너리 형태를 잃지 않도록 마지막 레벨의 왼쪽부터 채워나간다. 다음 스텝은 자신의 부모 노드와 비교해서 자신이 값이 작으면 부모 노드랑 자리를 바꾼다. 부모 노드가 자기보다 작을 때 까지 반복한다. 완전 이진 트리에서 이루어지니까 한번 돌 때 마다 o(logn)의 시간 복잡도를 가진다. 최소힙에서 노드 꺼내오기 최소힙에서 작은 값은 루트에있으니까 어렵지 않다. 루..