힙 알고리즘

2023. 1. 24. 20:37알고리즘

선택 정렬을 응용한 알고리즘인 힙 정렬은 힙의 특성을 이용하여 정렬을 수행합니다.

힙이란?


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

힙 정렬 이란?

힙 정렬은 힙을 사용하여 정렬하는 알고리즘입니다.

힙 정렬은 가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘입니다.
힙에서 가장 큰 값인 루트를 꺼내는 작업을 반복하고 그 값을 늘어놓으면 배열은 정렬을 마치게 됩니다.

힙으로 만든 후 -> 배열의 맨 오른쪽부터 루트값 채워 넣고 -> 다시 힙으로 만든 후  -> 루트값 채워 넣음

이렇게 배열의 정렬이 완료될 때까지 힙 만들기와 루트값 넣기를 반복하여 정렬합니다.

 

또 시스템 해킹(Pwnable)에도 힙이 있는데요

그때에 힙은 메모리 힙이라고 생각하시면 될 것 같습니다.

메모리의 스택 힙을 아이디어로 따서 힙 알고리즘을 만든 것이고 그 힙의 근원이 메모리의 힙으로 알면 됩니다.

 

 

'알고리즘' 카테고리의 다른 글

재귀 알고리즘이란  (0) 2023.01.23
검색 알고리즘이란  (0) 2023.01.22
알고리즘이란  (0) 2023.01.22
이진탐색이란  (0) 2023.01.11