ImYena

힙(Heap) 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)의 시간복잡도 소요, 이에 반해 힙은 O(logn) 소요 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용 힙 구조 최대값을 구하기 위한 구조(최대 힙, Max Heap)와 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류 할 수 있음 힙의 두 가지 조건 각 노드의 값이 최대 힙의 경우 해당 노드의 자식 노드가 가진 값보다 크거나 같고, 최소 힙의 경우 작거나 같아야 함 완전 이진 트리 ..

큐(Queue) 구조 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 예) 줄 서는 행위 FIFO(First-In, First-Out) 방식 또는 LILO(Last-In, Last-Out) 방식 기능 Enqueue(인큐) 큐에 데이터를 넣는 기능 Dequeue(디큐) 큐에서 데이터를 꺼내는 기능 특징 운영체제 혹은 인터넷/네트워크에서 자주 사용 스택과 꺼내는 순서가 반대 배열과 같이 특정 위치가 정해진 것이 아니라 데이터의 입력과 출력만 존재! 그렇기 때문에 큐는 특정 데이터를 정해서 출력하는 것이 불가능! 참고 : 어디에 큐가 많이 쓰일까? - 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 많이 사용(운영체제 참조) - 큐의 경우에는 장단점 보다는(특별히 언급되는 장단점이 없음), ..