힙3 [A* & Heap] Chapter 02. 힙 이론 우선순위 큐는 힙 트리 구조로 이뤄졌다. 힙트리도 이진트리의 일종이다. - 이진 트리의 개념 각 노드가 최대 두 개의 자식 노드를 가지는 트리 - 이진 검색 트리 특징 1) 왼쪽을 타고 가면 현재 값보다 작다 2) 오른쪽을 타고 가면 현재 값보다 크다 - 이진 검색 트리 문제 그냥 무식하게 추가하면, 한쪽으로 기울어져서 균형이 깨진다 트리 재배치를 통해 균형을 유지하는 것이 과제 (AVL, Red-Black) - 힙 트리 특징 1. [부모 노드]가 가진 값은 항상 [자식 노드]가 가진 값보다 크다. 2. 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다. - 힙 트리 구현 배열을 이용해서 힙 구조를 바로 표현할 수 있다. 1) i번 노드의 왼쪽 자식은 [(2 * i) + 1] 번 2) i번 노드의 .. 2023. 8. 8. [Programmers] (힙(Heap)) Lv 2. 더 맵게 https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr #include #include #include using namespace std;int solution(vector scoville, int K) { int answer = 0; priority_queue, greater> q; for (const auto& e : scoville) q.push(e); int first, second, result; while (true.. 2023. 7. 4. [Data Structure] 비선형 - Heap(힙) Heap(힙) Binary Tree(이진트리) 최소 힙 : 부모의 키 값이 자식의 키 값보다 작거나 같다. 루트 노드의 키 값이 트리의 최솟값 최대 힙: 부모의 키 값이 자식의 키 값보다 크거나 같다. 루트 노드의 키 값이 트리의 최댓값 최대 힙 → 힙 정렬 알고리즘 → 우선순위 큐 2023. 2. 21. 이전 1 다음
