heap

힙 (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#] 힙 (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..