René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Heap \u0026 우선순위 큐","articleBody":"## 힙 Heap\r\n\r\n완전 이진 트리의 일종으로 두가지 조건 충족\r\n\r\n1. 완전 이진 트리\r\n2. 최대 힙 (부모 노드값  \u003e 자식 노드값) , 최소 힙 (부모 노드 값 \u003c 자식 노드값)\r\n\r\n## 우선순위 큐 Priority Queue\r\n\r\n우선순위 큐는 각 요소가 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 나가는 특수한 큐\r\n\r\n1. 힙을 사용하여 효율적으로 구현 가능\r\n2. 삽입 -  새로운 요소를 힙의 마지막에 추가한 후 힙 정렬\r\n3. 삭제 - 힙의 루트 요소를 제거 하고 마지막 요소를 루트로 이동시킨 후 힙 정렬\r\n * 삽입: O(log n)\r\n * 삭제 (Olog n)\r\n * 탐색 (루트 요소 확인): O(1)\r\n \r\n \r\n### STL을 이용한 Heap 구현\r\n\r\n```cpp\r\n#include \u003ciostream\u003e\r\n#include \u003cvector\u003e\r\n#include \u003calgorithm\u003e\r\n\r\nint main() {\r\n    std::vector\u003cint\u003e heap = {10, 20, 30, 5, 15};\r\n\r\n    // 힙으로 변환\r\n    std::make_heap(heap.begin(), heap.end());\r\n\r\n    std::cout \u003c\u003c \"Initial max-heap: \";\r\n    for (int i : heap) std::cout \u003c\u003c i \u003c\u003c \" \";\r\n    std::cout \u003c\u003c std::endl;\r\n\r\n    // 힙에 요소 추가\r\n    heap.push_back(99);\r\n    std::push_heap(heap.begin(), heap.end());\r\n\r\n    std::cout \u003c\u003c \"After adding an element: \";\r\n    for (int i : heap) std::cout \u003c\u003c i \u003c\u003c \" \";\r\n    std::cout \u003c\u003c std::endl;\r\n\r\n    // 힙에서 최대 요소 제거\r\n    std::pop_heap(heap.begin(), heap.end());\r\n    heap.pop_back();\r\n\r\n    std::cout \u003c\u003c \"After removing the max element: \";\r\n    for (int i : heap) std::cout \u003c\u003c i \u003c\u003c \" \";\r\n    std::cout \u003c\u003c std::endl;\r\n\r\n    return 0;\r\n}\r\n```\r\n ### 우선순위 큐\r\n```cpp\r\n\r\n#include \u003ciostream\u003e\r\n#include \u003cqueue\u003e\r\n#include \u003cvector\u003e\r\n\r\nstruct Task {\r\n    int priority;\r\n    std::string description;\r\n\r\n    // 커스텀 비교 함수 (작은 값이 높은 우선순위)\r\n    bool operator\u003c(const Task\u0026 other) const {\r\n        return priority \u003e other.priority;\r\n    }\r\n};\r\n\r\nint main() {\r\n    std::priority_queue\u003cTask\u003e taskQueue;\r\n\r\n    // 요소 삽입\r\n    taskQueue.push({1, \"Low priority task\"});\r\n    taskQueue.push({3, \"High priority task\"});\r\n    taskQueue.push({2, \"Medium priority task\"});\r\n\r\n    std::cout \u003c\u003c \"Tasks in priority order: \";\r\n    while (!taskQueue.empty()) {\r\n        Task t = taskQueue.top();\r\n        std::cout \u003c\u003c \"(\" \u003c\u003c t.priority \u003c\u003c \", \" \u003c\u003c t.description \u003c\u003c \") \";\r\n        taskQueue.pop();\r\n    }\r\n    std::cout \u003c\u003c std::endl;\r\n\r\n    return 0;\r\n}\r\n```\r\n \r\n ","author":{"url":"https://github.com/psychehose","@type":"Person","name":"psychehose"},"datePublished":"2024-07-29T11:57:54.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/1/SquirtlesAlgorithmStudyS8/issues/1"}