힙

힙 (Heap) / 이진 힙 (Binary Heap)

정의힙 (heap)은 이진 힙 (binary heap)이라고도 하며, 최댓 값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조다. 힙은 다음과 같은 속성을 가지고 있다.완전 이진트리(Complete Binary Tree) 이다.부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다.키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음.힙의 종류1. 최대 힙 (Max Heap)부모 키값이 자식노드 키값보다 큰 힙Key(parent) ≥ Key(child)가장 큰 값이 루트노드에 있음2. 최소 힙 (Min Heap)부모 키값이 자식노드 키값보다 작은 힙Key(parent) ≤ Key(ch..

[C#] 우선순위 큐 개념과 힙을 통한 구현

우선순위 큐란? 큐(Qeueu)는 FIFO(First In First Out) 방식을 따르기 때문에, 입력 순서대로 출력되는 데이터 구조인 반면, 우선순위 큐(Priority Qeueu)는 입력 순서와는 무관하게 우선순위대로 출력되는 데이터 구조다. 시간 복잡도 우선 순위 큐는 Enqueue()시, 내부적으로 정렬을 해주거나 또는 탐색을 해주어야하는 로직이 필요하다. 우선 순위대로 정렬하거나 탐색하는 방법으로 얼마나 효율적으로 만드느냐가 주제의 핵심 포인트다. 이 글에서는 'O(N)'과 'O(logN)' 두 가지 방식을 다룬다. 우선순위 큐 구현 방법과 종류 이진 탐색'O(logN)'과 단순 선형 탐색 차이'O(N)' Queue의 Enqueue()시, 내부적으로 효율적인 탐색 방법이 필요하다. 간단한 구..

[C#] 힙 (Heap)

1. 힙이란? : 완전 이진 트리(Complete Binary Tree)의 일종. 여러 값의 데이터들 중 최대값과 최소값을 빠르게 찾아낼 수 있는 자료구조입니다. (시간복잡도로 따지면 O(logn)이 걸림) * 힙의 특징 - 중복 값을 허용 - 루트가 최대값(새로운 데이터가 추가될 때 부모노드와 크기를 비교해 크기가 더 큰 값을 부모노드로 올리기 때문) - 새로운 데이터를 추가할 때 작은 레벨 순서대로 채움(왼쪽부터) 2. 이진 탐색 트리와 힙의 차이 * 공통점 : 둘 다 이진 트리. * 차이점 - 힙은 이진 탐색 트리와 달리 중복 값을 허용. - 힙은 각 노드들이 부모노드의 데이터 값보다 작거나 같음. - 이진 탐색 트리는 말 그대로 탐색을 위한 자료구조이고, 힙은 최대값과 최소값 검색을 위한 자료구조..

C# 힙 구조 (Heap)

스택은 단순히 데이터를 넣고 뺄 수 있는 구조이며, System.ValueType을 상속하는 기본 데이터형(int, long, bool 등)만 저장할 수 있다. 힙은 예약된 주소 공간을 뜻한다. 최초에 프로세스가 초기화될 때 시스템은 프로세스 주고 공간 내에 하나의 힙을 생성한다. 이 힙을 프로세스의 기본 힙이라 하며, 기본 할당 크기는 1M로 정해져있다. 닷넷에서는 가비지 컬렉터가 자원을 관리하기 때문에 힙에 대한 함수를 직접 제공하지 않지만 Win32 API GetProcessHeap() 사용하여 현재 프로세스의 힙을 가져올 수 있다. using System.Runtime.InteropServices; public unsafe class Memory { static int ph = GetProcess..

[실1] 11286 - 절대값 힙

#include #include #include #include using namespace std; #define y first #define x second int main() { using pq_type = pair; cin.sync_with_stdio(0); cin.tie(0); priority_queue q; int n; cin >> n; for (int i = 0; i > val; if (val != 0) q.push({ abs(val), val }); else { if (q.empty()) cout

프로세스 메모리 구조와 스택 프레임 구조

프로세스 메모리 구조 프로세스의 메모리 구조는 Text, Data, Heap, Stack 영역으로 구분되어 있다. 프로세스 메모리 구조 Text 영역 : 프로그램 코드와 상수가 정의되어 있고, 읽기만 가능한 메모리 영역이기 때문에 데이터를 저장하려고 하면 분할 충돌을 일으켜 프로세스가 중지된다. Data 영역 : 전역 변수(Global variable)와 정적 변수(Static variable)가 저장되어 있는 영역이다. Heap 영역 : 프로그래머의 필요에 따라 동적 메모리 호출에 의해 할당되는 메모리 영역이다. c언어의 기준으로 malloc() 함수나 calloc() 함수에 의해 생성된 변수들이 이 곳에 할당된다. Stack 영역 : 함수 인자 값, 함수 내의 지역 변수, 함수의 반환 주소 등이 저장..