힙

1. 메모리 주소(Memory address)- 포인터를 알아가기 전에 데이터가 메모리에 저장되는 구조에 대해서 알아보자.- 다음 예시는 각각 다른 데이터타입을 가진 변수를 선언한 코드이다.#include int main(){ char a = 'A'; int b = '10'; double c = '123.45';} - 해당 코드를 실행하면 메모리에서 다음과 같이 데이터가 저장이 된다. - 해당 프로그램이 동작할 땐, CPU가 주소를 통해 특정 메모리 공간에 접근하게 된다.- 변수를 선언하게 되면 자료형의 크기에 맞게 공간이 확보가 되고, 해당 공간에 데이터를 기록한다.- 데이터가 담기는 공간의 시작 메모리 주소는 실행할 때 마다 달라진다.- 이러한 시작 메모리 주소는 데이터를 접근할 때 매우 ..

1. Priority Queue(우선순위 큐)?- 우선 Priority Queue를 설명하기 전에, Queue에 대해서 설명하고자 한다.- Queue는 FIFO(FIrst In First Out) 즉 선입선출, 먼저 집어 넣은 데이터가 먼저 나오는 자료구조이다.- 하지만 Priority Queue는 들어간 순서에 상관없이, 우선순위가 높은 데이터부터 먼저 나오는 것을 의미한다.2. 우선순위 큐의 메소드- 우선순위 큐의 메소드는 크게 3가지가 존재한다. i) insert() : queue에 데이터를 삽입한다.ii) delete() : queue에서 최대 우선순위 데이터를 삭제하고 그 값을 반환한다.iii) peek() : queue에서 최대 우선순위 데이터를 반환한다. 2.1. Qriority Queue ..

0. Review- 6-1 에서 우리는 Heap을 알아가는 동안 Max-Heap에 대해서 알아보았다.- 이번 챕터에서는 Max-Heap을 유지하게 해주는 Max-Heapify 에 대해서 알아볼 것이다. 1. Max-Heapify- Max-Heapify 절차는 최댓값 힙 속성을 유지한다.- 입력값은 배열 A, 그리고 배열의 인덱스 i를 받는다.- Max-Heapify는 LEFT(i), RIGHT(i)로 시작하는 Heap들이 이미 Max Heap이라는 것을 가정한다. - 하지만 A[i]가 자식노드보다 작을 경우 Max-Heap을 만족하지 않는다.- 그래서 A[i]를 아래에 있는 노드로 계속 흘려보내면서 Max-Heap을 만족하게 한다.- 다음 그림은 Max-Heapify의 동작을 보여준다. - (a)상황을 ..

1. Heaps?- 우선 힙을 저장하는 자료구조는 배열이다.- 일반적으로 이진 트리(Binary Tree)로 구현되는 완전 이진 트리의 형태다.- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.- 구현을 쉽게 하기 위해 0인 인덱스는 사용하지 않고 1부터 사용된다.- 그림으로 나타내면 다음과 같다. (트리의 높이는 log(n)이 된다.)  2. 힙에서의 부모노드와 자식노드의 관계i번째 노드- 부모 노드 인덱스 : i//2- 왼쪽 자식 노드 인덱스 : 2*i- 오른쪽 자식 노드 인덱스 : 2*i + 13. Max Heap- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 - 즉, 다음을 만족하는 Heap을 의미한다. A[parent(i)] >= A..