힙 알고리즘
2023. 1. 24. 20:37ㆍ알고리즘
선택 정렬을 응용한 알고리즘인 힙 정렬은 힙의 특성을 이용하여 정렬을 수행합니다.
힙이란?

힙은 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리입니다. 이때 부모의 값이 사직보다 항상 작아도 부모와 자식 요소의 관계만 일정하면 힙이라고 합니다.
힙 정렬 이란?

힙 정렬은 힙을 사용하여 정렬하는 알고리즘입니다.
힙 정렬은 가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘입니다.
힙에서 가장 큰 값인 루트를 꺼내는 작업을 반복하고 그 값을 늘어놓으면 배열은 정렬을 마치게 됩니다.
힙으로 만든 후 -> 배열의 맨 오른쪽부터 루트값 채워 넣고 -> 다시 힙으로 만든 후 -> 루트값 채워 넣음
이렇게 배열의 정렬이 완료될 때까지 힙 만들기와 루트값 넣기를 반복하여 정렬합니다.
또 시스템 해킹(Pwnable)에도 힙이 있는데요
그때에 힙은 메모리 힙이라고 생각하시면 될 것 같습니다.
메모리의 스택 힙을 아이디어로 따서 힙 알고리즘을 만든 것이고 그 힙의 근원이 메모리의 힙으로 알면 됩니다.
