'힙 트리' 태그의 글 목록
본문 바로가기
728x90

힙 트리2

C언어 - 힙 정렬 구현 코드 #include #define num 8 int node[] = {2,1,33,21,6,42,50,5}; void heapify(int n, int start, int *node) { int l,r,tmp; l = start*2+1; r = start*2+2; if(r>n) { return; } if(node[l] > node[start] || node[r] > node[start]) { if(node[l] > node[r]) { tmp = node[start]; node[start]=node[l]; node[l]=tmp; return heapify(n,l,node); } else { tmp = node[start]; node[start]=node[r]; node[r]=tmp; return heapify.. 2021. 5. 21.
힙 정렬(Heap Sort) 힙 정렬(Heap Sort)은 큌 정렬(Quick sort)과 병합 정렬(Merge Sort)과 같은 시간 복잡도 O(N*logN)를 가지고 있다. 힙 트리를 이용하는 정렬 방법이다. 힙 트리란 힙 트리의 조건 중 부모 노드의 값은 항상 자식 노드(하위 노드)의 값보다 크거나 작아야 한다. 힙 트리는 위의 조건은 만족하는 정렬은 두가지 뿐이다. 최대 힙(Max Heap), 최소 힙(Min Heap) 힙 트리 구조의 자녀 트리 사이에는 대소관계는 정해지지 않는다. 또한 힙 트리는 완전 이진 트리를 조건으로 가지고 있어야 한다. 왼쪽부터 차근차근 채워나가며 1~n까지 만들어지는 트리구조이다. 완전 이진 트리의 장점은 트리를 배열로 쉽게 구현이 가능하며, 부모 노드와 자식 노드 간에 관계를 수식화 할 수 있다.. 2021. 5. 14.
728x90

티스토리툴바