Dog foot print

heap 이란 ? heap 은 우선순위 큐를 위해서 만들어진 트리자료구조이다. heap은 부모노드와 자식노드의 대소관계에 따라 최대힙(Max heap)과 최소힙(Min heap)으로 나뉜다. heap의 특징 heap은 완전이진트리의 형태이다. 완전이진트리 설명보러가기 heap은 트리내에서 중복된 값을 허용한다. heap은 느슨한 정렬(반 정렬) 상태를 가진다. 반 정렬 이라는 의미는 자식노드가 부모의 노드보다 무조건 크거나 작다. 그러나 전체트리를 볼 때는 가장 아래에 있는 노드가 가장 작거나 큰 값은 아니라는 의미이다. Max heap 최대 힙 최대힙은 다음과 조건을 항상 만족한다. 자식노드 value >= 부모노드 value Min heap 최소 힙 최소힙은 다음과 같 은 조건을 항상 만족한다. 자식..

해당 포스팅은 큐와 트리를 이해했다는 가정하에 작성되고 있습니다. 큐와 트리에 이해도가 없는 분들은 본 포스팅을 보기 전 큐와 트리에 대한 포스팅을 먼저 읽어주시기 바랍니다. 우선순위 큐란 ? 우선순위 큐는 일반적인 큐와 거의 동일하다. 큐는 해당자료구조에 들어온 순서대로 배출이 된다. 다만 우선순위 큐는 우선순위큐는 먼저나가는 순서를 들어온 순서 뿐만 아니라 다른 조건에 의하여 들어온 데이터에 우선순위를 부여해 순위에 맞게 배출한다. 어찌보면 일반적인 큐도 우선순위큐가 될 수 있는데 배출되는 순서를 해당 큐에 들어온 순서에 의거하여 우선순위를 부여하여 배출하기 때문이다. 우선순위 큐의 사용 예 우선순위 큐는 우리의 일상에서도 친근하게 사용되고 있다. 유니버셜 스튜디오랜드같은 해외 외국 놀이공원에서는 일..