분류 전체보기211 [강의노트] 힙과 힙정렬 - 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. [실습] 삽입식 힙 생성 삽입식 힙 생성 포스트에 게시된 것은 알고리즘 수업자료에 대한 기록입니다. 제가 작성한 소스코드에 대한 카피를 금지합니다. 힙은 이진트리로 구현된 우선순위 큐다. 여기서 이진트리를 배열을 이용해서 구현하면 순차트리 형태, ==> 순차힙 연결리스트를 이용하면 연결트리 형태로 구현할 수 있다. ==> 연결힙 우선순위 큐의 각 항목은 (키, 원소) 쌍이며 이진트리의 각 노드로 구현된다. 이진트리의 루트에 최소 키를 저장한 경우 최소힙, 반대로 최대 키를 저장한 경우 최대힙이라고 부른다. 힙 생성은 삽입식과 상향식의 두 가지 방식이 있다. 삽입식은 모든 키 들이 미리 주어진 경우, 또는 키들이 차례로 주어지는 경우 양쪽에 적용이 가능하다. 상향식은 모든 키 들이 미리 주어진 경우에만 적용 가능하다. 즉, 다시 .. 2021. 9. 5. 2021 09 02 보호되어 있는 글 입니다. 2021. 9. 2. [강의노트] 우선순위 큐와 힙 우선순위 큐 우선순위 큐가 무엇인가? 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조. 데이터를 우선순위에 따라 처리하고 싶을 때 사용함. 스택 : 가장 나중에 삽입된 데이터를 추출 큐 : 가장 먼저 삽입된 데이터를 추출 우선순위 큐 : 가장 우선순위가 높은 데이터를 추출 우선순위 큐를 구현하는 방법 1. 단순히 리스트를 이용하여 구현. 2. 힙을 이용하여 구현 힙(Heap)의 특징 힙은 완전 이진 트리 자료구조의 일종이다. 여기서 완전 이진 트리란 힙의 높이를 h라 했을때 i=0 , . . ., h-1 에 대해 깊이 i인 노드가 2^i개 존재 하고 깊이 h-1 에서 내부노드(자식이 있는 노드)들은 외부노드(자식이 없는 노드)들의 왼쪽에 존재하는 트리 쉽게 말하면 루트 노드부터 시작해서 자식노드가 .. 2021. 9. 2. 이전 1 ··· 23 24 25 26 27 28 29 ··· 53 다음
