지난 학기들의 기록/알고리즘28 [강의노트] 힙과 힙정렬 - 3 힙과 힙정렬 - 3 아래의 글에 이어지는 글입니다. [강의노트] 힙과 힙정렬 - 1 힙과 힙정렬 힙이란? 내부노드에 키를 저장하며 다음 두가지 속성을 만족하는 이진트리 ( 외부노드에는 키를 저장하지 않는다는 것 .) 힙순서(heap-order): 루트를 제외한 모든 내부노드 v에 대해, ke man-25-1.tistory.com [강의노트] 힙과 힙정렬 - 2 힙과 힙정렬 - 2 아래의 글에 이어지는 글입니다. [강의노트] 힙과 힙정렬 - 1 힙과 힙정렬 힙이란? 내부노드에 키를 저장하며 다음 두가지 속성을 만족하는 이진트리 ( 외부노드에는 키를 저장하 man-25-1.tistory.com 상향식 힙 생성 https://man-25-1.tistory.com/156 [실습] 상향식 힙 생성 상향식 힙 생성.. 2021. 9. 25. [강의노트] 힙과 힙정렬 - 2 힙과 힙정렬 - 2 아래의 글에 이어지는 글입니다. [강의노트] 힙과 힙정렬 - 1 힙과 힙정렬 힙이란? 내부노드에 키를 저장하며 다음 두가지 속성을 만족하는 이진트리 ( 외부노드에는 키를 저장하지 않는다는 것 .) 힙순서(heap-order): 루트를 제외한 모든 내부노드 v에 대해, ke man-25-1.tistory.com 배열에 기초한 힙 구현 이미 지난 실습에서 우리는 배열을 이용해서 힙을 생성하는 코드를 작성해보았다. https://man-25-1.tistory.com/154?category=938895 [실습] 삽입식 힙 생성 삽입식 힙 생성 포스트에 게시된 것은 알고리즘 수업자료에 대한 기록입니다. 제가 작성한 소스코드에 대한 카피를 금지합니다. 힙은 이진트리로 구현된 우선순위 큐다. 여기.. 2021. 9. 7. [실습] 상향식 힙 생성 상향식 힙 생성 https://man-25-1.tistory.com/154 [실습] 삽입식 힙 생성 삽입식 힙 생성 포스트에 게시된 것은 알고리즘 수업자료에 대한 기록입니다. 제가 작성한 소스코드에 대한 카피를 금지합니다. 힙은 이진트리로 구현된 우선순위 큐다. 여기서 이진트리를 배 man-25-1.tistory.com 저번 포스트에서 다루었던 삽입식 힙 생성에 이어서 이번에는 상향식 힙 생성을 다루어보자. 힙 생성에 대한 전반적인 이야기는 위 게시물을 참고하면 되고, 이번에는 삽입식 힙 생성과 상향식 힙 생성의 차이점에 중점을 두고 다루어보겠다. 힙 생성은 삽입식과 상향식의 두 가지 방식이 있다. 삽입식은 모든 키 들이 미리 주어진 경우, 또는 키들이 차례로 주어지는 경우 양쪽에 적용이 가능하다. 상향.. 2021. 9. 7. [강의노트] 힙과 힙정렬 - 1 힙과 힙정렬 힙이란? 내부노드에 키를 저장하며 다음 두가지 속성을 만족하는 이진트리 ( 외부노드에는 키를 저장하지 않는다는 것 .) 힙순서(heap-order): 루트를 제외한 모든 내부노드 v에 대해, key(v) >= key(parent(v)) # 즉 자식노드가 부모노드보다 같거나 크다. ( 최소힙의 힙순서를 말함) 완전이진트리(complete binary tree): 힙의 높이를 h라 했을 때, i = 0 , ... , h - 1 에 대해 깊이 i인 노드가 2^i개 존재한다. # 즉 루트노드 부터 시작해서 트리의 하단으로 갈수록 2의 제곱만큼 개수가 늘어나는 것을 말함 깊이 h - 1 에서 내부노드들은 외부노드들의 왼쪽에 존재해야한다. # 왼쪽부터 채워지는 것을 말함 힙의 높이 n개의 키를 저장한 .. 2021. 9. 6. 이전 1 2 3 4 5 6 7 다음
