코딩하기 좋은 밤 코딩하기 좋은 밤

힙소팅

• [알고리즘] Heap sorting

  SW/Algorithm 2018. 1. 6. 16:55

  Heap sort 코드링크 insert delete min(max) Complete Binary Tree 순서대로 채워져있는 트리 배열사용 레밸의 맨 왼쪽은 2^h 루트에서 마지막 노드 = floor(logN) 2^h ~ 2^(h+1)-1개 노드 그 노드의 부모는 floor(k/2) 그 노드의 왼쪽 자식 2k, 오른쪽 2k+1 Binary Heap Binary Heap 특징 : 컴플릿트 바이너러 / min heap(부모는 자식보다 작거나 같다.) / max heap(부모는 자식보다 크거나 같다.) insert : 마지막 노드에 추가 하고 위치로 GO! (fix heap) delete(min/max) : 루트만 지울 수 있다. 루트를 삭제 마지막 노드를 루트로 올림. fix heap! Heap Constr..

  Read More