# MinHeap
백준 1927, 최소 힙 - Heap / PriorityQueue
https://www.acmicpc.net/problem/1927 풀이 ① 1. 아이디어 1) x > 0 인 경우 PriorityQueue에 x 추가 => 최소값이 먼저 오도록 정렬 2) x == 0 인 경우 PriorityQueue가 not empty => PriorityQueue에서 remove 및 출력 PriorityQueue가 empty => 0 출력 2. 자료구조 PriorityQueue: 입력 정수 x 저장 및 정렬 3. 시간 복잡도 PriorityQueue / Heap 의 시간 복잡도 =>
[자료구조|알고리즘 개념] Greedy 알고리즘 (최대힙, 최소힙)
👨🌾 그리디(Greedy) > * 현재 상태에서 가장 좋은 것을 선택한다. 정렬 된 상태에서 많이 사용한다. ex) 동전 잔돈 문제 - 1600원을 거슬러줘야 할 때 , 잔돈의 종류가 [1000,500,100,50]이 있다면 50원 여러개 주기보다는 1000원 1장,500원 1개, 100원 1개로 돌려준다. (단, 잔돈 문제는 큰 금액이 작은 금액의 배수여야 한다. 배수가 아니라면, Knapsack, DP로 풀이해야 한다.) Greedy의 정렬 Greedy 에서 정렬은 가장 중요하다.* 앞에서부터 정렬할 것인지, 뒤에서부터 정렬할 것인지 결정*해야한다. (결정하는 방법 : 증명하기 어려우니 반례를 생각할 것) 🗣 최대힙(Max Heap) 
[Data Structure] 힙(HEAP)이란 무엇인가? - (1)
Heap 이란 최대값 또는 최소값을 빨리 뽑아내고 싶을 때 사용하는 자료구조이며, 최대값을 우선순위로 뽑고 싶으면 MaxHeap을, 최소값은 MinHeap을 사용한다. Heap을 사용하는 이유는 For문 탐색보다 빠르게 Min, Max 값을 탐색할 수 있기 때문이다. For문을 사용하면 Min값을 구하기 위해, 반드시 모든 값과 비교를 하며 최소값을 갱신해야하지만, Heap의 경우 O(logⁿ)의 굉장히 빠른 속도로 Min, Max 값을 구할 수 있다 Min Heap의 경우, 값을 저장할 때는 이진트리 형태로 값을 저장하지만, 이진트리와 다른 점은 Root부분에 항상 Min값을 위치시킨다는 것이며, 저장(Push) 및 출력(Pop)이 되더라도 항상 Root부분은 Min값을 유지해야 한다. 즉, 왼쪽에는 작은 값을 저장하는 이진트리와 달리 Heap은 자식노드 값이 항상 부모 노드 값보다 크다. ** Push는 값이
Javascript 자료구조 07 : Heap
Heap(힙) 힙은 '최대값 혹은 최소값'을 빠르게 찾기 위한 완전 이진 트리 (이전 글에서 다뤘던 이진 탐색 트리는 '탐색'을 빠르게 하기 위한 구조) 완전 이진 트리 : node를 삽입할 때 최하단 왼쪽 node부터 차례로 삽입하는 트리. 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있고, 마지막 레벨의 node는 왼쪽부터 채워져있는 구조. Min Heap(최소 힙) 완전 이진 트리 각 node의 값은 자식 node가 가진 값보다 작거나 같다. (root의 값이 가장 작다.) Max Heap(최대 힙) 완전 이진 트리 각 node의 값은 자식 node가 가진 값보다 크거나 같다. (root의 값이 가장 크다.) insert(데이터 삽입) 완전 이진 트리의 조건에 따라서 data를 삽입한다. swap : 새로 삽입한 값과 그 부모 node를 비교하여 위치를 맞바꾼다.
[ Heap ] Max Heap과 Min Heap
2학년때 배웠던 MAX-HEAP, MIN-HEAP.. 다 까먹었다. 고로 정리한다. Perfect Binary Tree 포화 이진 트리는 leaf node를 제외한 모든 노드의 자식의 수가 두개인 트리이다. leaf node는 당연히 자식의 수가 0개이다. 또한, * 모든 leaf node의 depth가 같아야 한다*. 그냥 한마디로 말하자면 어디 하나 구멍난 것 없이 차곡차곡 잘 채워진 이진 트리를 말한다. perfect 이진트리.... 모든 leaf node의 depth가 같은 조건 덕분에, 높이가 h인 트리의 전체 노드 개수는 $2^{h-1}$개 이다. Complete Binary Tree `Perfect Binary Tree
[ BOJ ] 1927번: 최소 힙
오늘의 한줄평 > ^는 비트연산자이다. 제곱승을 계산하고 싶으면 pow를 써야 함^^ 1927번 : 최소 힙 뭐 따로 쓸 말도 없다. ^는 비트 연산자이다 ^를 제곱 연산자로 착각해서, ^를 연신 써 놓고 잘 되는 케이스만 넣어놨으니 3%에서 당연히 틀려먹지. 제곱승을 계산하려면 pow함수를 이용해야 한다 미래의 나야 문제 풀이 사실 최소 힙은 priorityqueue와 결과가 같다. 따라서 그냥 queue 라이브러리 안에 있는 priorityqueue에 정렬 조건을 greater로 사용하면 금방 풀리는 문제이긴 하다. 나는 힙이라는 자료구조 자체를 공부하기 위해 이 문제를 풀었으니, 구조체 형식으로 만들어보았다. 문제에서 힙 안에 들어가는 수는 $1$부터 $2^{31}-1$까지의 수라고 범위를 줬기 때문에, 최소 힙임을 고려하여 사용하지 않는 노드를 $2^{31}$로 초기화하였다. 이때, int의