최대 힙은 부모 값이 자식 값보다 작지 않은 완전이진트리입니다. 새 값은 마지막 자리에 넣고 부모와 비교해 필요한 만큼 교환합니다.
루트에서 최댓값을 바로 읽을 수 있고, 삽입·제거는 트리 높이만큼 진행합니다. 전체 원소가 정렬된 것은 아니므로 임의 순위의 값을 바로 읽을 수는 없습니다.
언제 쓰나
작업 예약이나 최단 경로 탐색처럼 다음 우선순위 항목을 자주 꺼낼 때 씁니다.
힙 우선순위 큐
Heap priority queue
가장 높은 우선순위 값을 루트에 두고 삽입할 때 위로 올립니다.
···
<div class="v"><header><b>MAX HEAP</b><span id="state"></span></header><main><div class="tree" id="tree"></div><div class="insert">insert <b>9</b> ↑</div></main><footer>parent ≥ children</footer></div>.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .tree{height:70%;display:grid;grid-template-columns:repeat(4,1fr);grid-template-rows:repeat(3,1fr);place-items:center}.node{width:28px;height:28px;border:1px solid var(--line);border-radius:50%;display:grid;place-items:center;font:700 .9em ui-monospace,monospace}.node:nth-child(1){grid-column:2/4}.node:nth-child(2){grid-column:1/3}.node:nth-child(3){grid-column:3/5}.node:nth-child(4){grid-column:1}.node:nth-child(5){grid-column:2}.node:nth-child(6){grid-column:3}.node:nth-child(7){grid-column:4}.insert{text-align:center;color:var(--muted)}.insert b{color:var(--accent)}const steps=[[8,6,7,2,4,5,9],[8,6,9,2,4,5,7],[9,6,8,2,4,5,7]];let s=0;function draw(){document.getElementById("tree").innerHTML=steps[s].map((v,i)=>"<div class=\"node "+(v===9?"active":"")+"\">"+v+"</div>").join("");document.getElementById("state").textContent=["append","swap parent","root restored"][s];s=(s+1)%3}draw();setInterval(draw,1050)