René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Heap \u0026 우선순위 queue","articleBody":"## 1. 힙(Heap) 자료구조\r\n\r\n- **정의**: 힙은 우선순위 큐를 구현하기 위해 고안된 완전 이진 트리 형태의 자료구조\r\n- **장점**: 여러 개의 값 중 최댓값 또는 최솟값을 빠르게 찾을 수 있다.\r\n- **특징**:\r\n  - 부모 노드와 자식 노드 간에 대소 관계가 성립\r\n  - **힙의 종류**:\r\n    1. **최대 힙(Max-Heap)**: (부모노드 \u003e= 자식노드) ![[Pasted image 20240708203717.png | 400]]\r\n    2. **최소 힙(Min-Heap)**:  (부모노드 \u003c= 자식노드) \r\n       - ![[Pasted image 20240708191256.png | 400]]\r\n- **함수 구현**:\r\n  - **Min-Heapify()**:\r\n    - 부모 노드로 올라가며, 부모보다 자신의 값이 더 작은 경우 위치를 교체(위가 작게)\r\n    - 새로운 원소가 삽입되면, 시간 복잡도 O(log N)으로 힙의 성질을 유지\r\n\r\n---\r\n\r\n## 2. 큐(Queue) 자료구조란?\r\n\r\n- **정의**: 큐는 First In First Out(FIFO) 구조를 가지는 자료구조\r\n- **특징**: 먼저 들어간 데이터가 먼저 나오는 구조\r\n\r\n---\r\n## 3. 우선순위 큐(Priority Queue)\r\n\r\n- **정의**: 들어간 순서에 상관 없이, 우선순위가 높은 데이터가 먼저 추출되는 자료구조\r\n- **특징**:\r\n  - 우선순위가 가장 높은 데이터를 가장 먼저 삭제\r\n  - **예시**: 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인하는 경우.\r\n- **구현 방법**:\r\n  1. **리스트를 이용한 구현**:\r\n     - 데이터를 넣은 후 가장 큰 데이터를 뽑아 추출합니다.\r\n     - **시간 복잡도**:\r\n       - 삽입 시간: O(1) (단순히 리스트의 끝에 삽입)\r\n       - 삭제 시간: O(N) (우선순위가 높은 데이터를 찾기 위해)\r\n  2. **힙을 이용한 구현**:\r\n     - **시간 복잡도**:\r\n       - 삽입 시간: O(log N)\r\n       - 삭제 시간: O(log N)\r\n     - 배열이나 연결 리스트보다 힙을 이용하여 구현하는 것이 효율적입니다.\r\n\r\n---\r\n\r\n\r\n## 4. 스택(Stack)\r\n\r\n- **정의**: 스택은 가장 나중에 삽입된 데이터가 먼저 추출되는 자료구조\r\n- **특징**: Last In First Out(LIFO) 구조를 가짐\r\n\t1. 완전 이진 TREE : 위에서부터 2개씩 계속 나아가는~\r\n\t2. 부모 NODE \u003c 자식 NODE : 윗쪽이 아래쪽보다 작아야한다. 위로 갈수록 숫자가 작다.\r\n","author":{"url":"https://github.com/hnjgg","@type":"Person","name":"hnjgg"},"datePublished":"2024-07-30T05:51:11.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/5/SquirtlesAlgorithmStudyS8/issues/5"}