본문 바로가기
728x90

heap3

[Algorithms] Heap sort(힙 정렬)란 무엇인가요? * 2020년 4월 29일 자 포스트를 업데이트한 포스트입니다.*포스트 난이도: HOO_Junior# Heap Sort: 쌓여있는 데이터를 정렬하는 방법Heap이란 단어를 영어사전에서 찾아보면 "쌓여있는", "더미" 등의 뜻을 확인할 수 있다. 즉, Heap sort (힙 정렬)는 많은 양의 데이터를 정렬하는 방법이다. Heap sort는 알고리즘에서 여러 가지 정렬 방법 중 하나로, 데이터 값을 최댓값 또는 최솟값 기준으로 정렬할 때 사용한다. 최댓값 또는 최솟값으로 정렬하는 것을 한국어로는 힙 정렬(Heap sort)이라고 하며, 오름차순 또는 내림차순으로도 표현할 수 있다. Heap sort는 다른 정렬 방법과 달리 시각적으로 표현할 때 트리 형태로 나타낼 수 있다. 1차원 배열 형태에서 정렬하는 .. 2024. 12. 31.
[Example Codes]make_heap(v.begin(), v.end()), v.push_back(), push_heap(v.begin(), v.end()), pop_heap(v.begin(), v.end()) make_heap(v.begin(), v.end()), v.push_back(), push_heap(v.begin(), v.end()), pop_heap(v.begin(), v.end()) // WhoisHOO // C++에 빠지다 // Example Codes of Heap #include #include #include using namespace std; int main() { vector v = { 5,8,10,95,1,87,85,49 }; make_heap(v.begin(), v.end()); v.push_back(26); push_heap(v.begin(), v.end()); v.push_back(28); push_heap(v.begin(), v.end()); pop_heap(v.begin().. 2020. 4. 30.
heap sort(힙 정렬) Full Binary Trees vs Complete Binary Trees Full Binary Tree vs Complete Binary Tree heap sort를 공부하다 보면 Full binary tree와 Complete binary tree에 대한 용어를 들어본 적이 있을 겁니다. 예를 들어, 이런 형태의 배열이 존재한다고 가정해봅시다. heap sort를 사용하여 해당 배열을 정렬한다면, 맨 처음 꼭대기에 있는 노드를 제외하고 2개씩 나누어 왼쪽부터 정렬해야 합니다. 마치 이렇게 말이죠. 이런 식으로 배열을 나누고 Tree 형태로 표현하게 되면, 요런 형태의 tree가 나오게 됩니다. heap sort를 하진 않았지만 이런 방식으로 표현한 다음에 최솟값이나 최댓값 정렬을 하게 됩니다. 위의 tree를 살펴보면 모든 노드들은 자신의 child 노드를 2개씩 가지고 있.. 2020. 4. 29.
728x90