힙 정렬2 알고리즘 6장 - 정렬 문제 : 힙 정렬(2) - 알고리즘 6장- 정렬 문제 : 힙 정렬(2) - 앞 장에서 힙 정렬에 대한 개념을 알아보았다면 이번 장에서는 힙 구조를 만드는 것에 대해 중점을 두고 힙 정렬에 대해 살펴볼 것이다. 따라서 개념에 대한 부분을 보고자 하면 알고리즘 5장을 보면 될 것이다. Max 힙 구조를 만드는 코드를 한 번 살펴보자. Max 힙 구조는 부모 노드의 값이 자식 노드의 값보다 큰 이진 트리 구조를 나타낸다. Max 힙을 만드는 방법은 위에서 밑으로 만드는 것이 아니라 밑에서 위로 만든다고 할 수 있다. 만약 위에서부터 만들게 되면 밑으로 내려갈 때 마다 Max 힙의 구조를 만족시키는지를 확인해야하지만 밑에서 만들면 밑에서 트리 구조를 만족하는지만 생각하면 되기 때문에 수행 시간에서 단축될 수 있다. 여기서 length의 .. 2017. 6. 7. 알고리즘 5장 - 정렬 문제 : 힙 정렬(1) - 알고리즘 5장- 정렬 문제 : 힙 정렬(1) - 힙 정렬은 힙 구조의 특성을 이용한 정렬이다. 수행 시간은 작은 형태로 쪼개는 합병 정렬 방법의 수행시간인 O(nlgn)과 동일하고 삽입 정렬과 동일한 제자리 정렬을 한다. 힙의 형태는 완전 이진 트리에 가까운 형태이다. 트리의 형태는 부모 노드와 자식 노드로 이루어져 있는데 부모 노드는 상위에 있는 성분이고 자식 노드는 부모 노드에 연결된 성분을 의미한다. 이는 맨 처음에 존재하는 노드를 제외하고 모든 성분은 부모 노드가 되면서 자식 노드가 될 수 있다. 이진 트리의 경우 각 부모 노드에 연결된 자식 노드의 수가 2이하인 경우를 의미하고 완전 이진 트리는 맨 처음 노드인 Root 노드부터 제일 마지막 노드인 Leaf 노드까지 빠짐없이 채워져 있는 트리를 .. 2017. 6. 6. 이전 1 다음
