# MaxHeap
[자료구조] Python으로 MinHeap, MaxHeap 구현해보기
MinHeap MaxHeap > reference https://daimhada.tistory.com/108
Python 최대힙 구현하기 백준 11279
알고리즘을 하려면 이런 것 구현은 스스로 해야한다고 해서 Python을 통해서 구현해 봤다. 먼저 MaxHeap에 대해서 말하자면! 인터넷에서 찾아본 말로는 각 최대트리면서 완전이진트리 각 노드의 키값이 그 자식의 키값보다 작지않은 트리이다. 한마디로 최대값(?) 순으로 정렬된 완전이진트리라는 말이다. 아예 배열이 최대값이라는 말은 아니고 부모노드는 자식노드보다 작지만 않으면 된다. 목적은 가장 큰 값을 빠르게 찾기 위한 것! Heap이라는 완전 이진트리의 배열 안에 어떠한 원소를 집어넣는 순간 촤르륵 하면서 배열이 정렬되는 것이 MaxHeap이다. 사실 이해는 했는데 개념을 멋있게 설명을 못하겠음;; 인터넷에 맛깔나게 설명한거 있으니까 그거를 찾아보셈용;; 왜냐하면 이 블로그를 쓰는 이유는 내가 생각하기에 혼자힘으로 으쌰으쌰 풀어내서 기분좋아서 쓰는거니까 ㅎ; MaxHeap 처음에는 그냥 조빱인줄 알았다. 그래서 간단하게 생각한 것이 1. 추가 (
[Python/Baekjoon] 1939. 중량제한
💬 문제 문제 난이도: 백준 골드 3 문제 링크: https://www.acmicpc.net/problem/1939 ❗️접근 방법 시작점에서 끝점까지 갈 때 싣고 갈 수 있는 최대 중량을 묻는 문제이다. 시작점부터 끝점까지 여러 다리를 건너는 경우가 생길 것이고, 이때에는 제일 무게 제한이 낮은 것이 싣고 갈 수 있는 최대 중량이 될 것이다. (min 사용) 시작점부터 끝점까지 가는 경로가 1개 이상 나올텐데 그 중에서는 최대이어야 한다. (maxHeap 사용) ✅ 정답 코드 ✍️ 헷갈렸던 부분 시작점부터 끝점까지 가는 과정에서는 최솟값을 구해야하고 끝점에 도달했을 때에 얻게 되는 결과값들 중에서는 최댓값을 구해야 하기 때문에 minHeap을 써야 할지, maxHeap을 써야 할지 헷갈렸다. 결과적으로 얻고 싶은 것은 시작점에서 끝점에 도달했을 때의 최댓값이기 때문에 maxHeap을 사용하고, 일반적인
Data Structure 004 | Heap
어서와 자료구조와 알고리즘은 처음이지? 의 강의를 듣고 작성된 글입니다. 힙(Heap) 이진 트리(binary tree)의 한 종류이며 이진 힙(binary 힙)이라고도 부른다. 데이터 원소들의 순서를 교묘하게 표현한 트리이다. 데이터의 정렬에도 이용할 수 있으며 데이터를 정렬하는 알고리즘을 힙 정렬(heap sort)라고도 부른다. Max heap & Min heap 이진트리 노드탐색, 파이썬 Heapq 모듈 출처 : ht
[자료구조|알고리즘 개념] 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