HeapSort 검색 결과
1 개의 검색 결과가 있습니다.
Algorithm

자료구조 :: 힙 정렬 Heap sort (c/c++ 구현)

힙 정렬 Heap sort 힙 정렬은 힙 트리를 이용해서 정렬을 하는 방법 힙 트리란 트리구조에서 자식노드보다 부모노드가 큰 상태를 뜻한다. 왼쪽 트리를 보면 부모(5)가 자식(2와 3) 보다 크다. 그래서 힙트리이다. 오른쪽 트리는 부모(4)가 자식(6)보다 작다. 그래서 힙트리가 아니다. 힙정렬은 위와 같은 힙트리를 만들면서 정렬을 한다. 위와 같은 이진 트리가 있다. 현재 이 트리는 힙 트리 상태가 아니다. 5와 4, 3 노드를 보자. 4와 5를 바꿔, 힙 트리 상태로 바꿔준다. 그 왼쪽 아래 노드 또한 4와 6을 바꿔서 힙 상태로 바꿔준다. 다시 5와 6을 바꿔 힙상태로 바꿔준다. 이렇게 왼쪽은 힙상태가 되었다. 나머지 오른쪽을 힙상태로 바꿔줘야 한다. 3과 8을 바꿔 힙상태로 만들어준다. 8과 ..

2018. 4. 29. 20:35