Show code
```html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Heap Sort Visualization</title>
<style>
body { background: #111; display: flex; justify-content: center; align-items: center; height: 100vh; margin: 0; font-family: monospace; color: white; }
#controls { position: absolute; top: 20px; left: 50%; transform: translateX(-50%); padding: 10px; background: rgba(0, 0, 0, 0.7); border-radius: 5px; color: white; }
canvas { border: 1px solid #333; background: #222; }
</style>
</head>
<body>
<div id="controls">Swaps: <span id="swapCount">0</span></div>
<canvas id="heapCanvas"></canvas>
<script>
const canvas = document.getElementById('heapCanvas');
const ctx = canvas.getContext('2d');
const N = 80;
let bars = [];
let swapCount = 0;
let stepIndex = 0;
let animationState = 'INITIALIZING'; // States: 'BUILDING', 'SORTING', 'FINISHED'
let animationFrameId = null;
canvas.width = 900;
canvas.height = 400;
const BAR_WIDTH = canvas.width / N;
function initializeBars() {
bars = Array(N).fill(0).map(() => Math.floor(Math.random() * 30) + 1);
swapCount = 0;
stepIndex = 0;
document.getElementById('swapCount').textContent = '0';
}
function drawBars(highlight = [], swap = []) {
ctx.clearRect(0, 0, canvas.width, canvas.height);
for (let i = 0; i < N; i++) {
const height = bars[i] * 4; // Scale factor for visibility
let color = '#4CAF50';
if (swap.includes(i)) {
color = '#FFEB3B'; // Highlighted element
} else if (highlight.includes(i)) {
// Sorted tail area or current heap boundary
color = '#2196F3';
} else if (i === 0 || i === N - 1) {
color = '#555'; // Borders
}
ctx.fillStyle = color;
ctx.fillRect(i * BAR_WIDTH, canvas.height - height, BAR_WIDTH - 2, height);
}
}
// ----- Heap Sort Logic (State Machine) -----
function siftDown(arr, startIdx, endBound) {
let parent = startIdx;
let currentChild = startIdx + 1;
while (currentChild <= endBound) {
let left = 2 * Math.floor((currentChild - startIdx) / 2) + startIdx;
let right = 2 * floor((currentChild - startIdx) / 2) + 1 + startIdx;
let largest = currentChild;
if (left <= endBound && arr[left] > arr[largest]) {
largest = left;
}
if (right <= endBound && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== currentChild) {
swap(arr, currentChild, largest);
currentChild = largest;
} else {
break;
}
}
}
function heapify(arr, startIdx, endBound) {
let parent = Math.floor((startIdx + endBound) / 2) - 1;
for (let i = Math.floor((startIdx + endBound) / 2) - 1; i >= startIdx; --i) {
siftDown(arr, i, endBound);
}
}
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
swapCount++;
return { i: i, j: j };
}
// Animation Steps Storage
let animationSteps = [];
function captureStep(currentArray, highlightIndices, swapPair) {
animationSteps.push({
array: [...currentArray],
highlight: [...highlightIndices],
swap: swapPair || []
});
}
// Phase 1: Build Heap
function buildHeapAnimation() {
const arr = [...bars];
let steps = [];
for (let i = Math.floor(N / 2) - 1; i >= 0; --i) {
steps.push({ array: [...arr], highlight: [i], swap: [] }); // Initial state before siftDown
siftDown(arr, i, N - 1);
// Capture the step after sifting down completes (swaps are handled inside siftDown/swap calls)
steps.push({ array: [...arr], highlight: [], swap: [] });
}
return steps;
}
// Phase 2: Sorting and Heapify Steps
function sortHeapAnimation() {
let arr = [...bars];
let steps = [];
const maxHeapSize = N - 1;
for (let i = N - 1; i > 0; --i) {
// Swap root (arr[0]) with current end element (arr[i])
let swapPair = swap(arr, 0, i);
steps.push({ array: [...arr], highlight: [i], swap: swapPair }); // Mark the sorted element
// Restore heap property on remaining elements (heap size shrinks by 1)
siftDown(arr, 0, i - 1);
steps.push({ array: [...arr], highlight: [], swap: [] }); // Capture after sifting down
}
return steps;
}
function setupAnimation() {
animationSteps = [];
// 1. Build Phase (Max-Heap)
let buildSteps = buildHeapAnimation();
animationSteps.push(...buildSteps);
// Reset state for sorting phase visualization
bars = [...arrays[...animationSteps.length - 1].array];
// 2. Sort Phase
let sortSteps = [];
sortSteps.push({ array: [...bars], highlight: [], swap: [] }); // Initial view before first sort step
for (let i = N - 1; i > 0; --i) {
// Swap root with arr[i]
let currentArr = [...bars];
let tempSwapArray = currentArr;
tempSwapArray[0] = bars[i];
tempSwapArray[i] = bars[0];
swapCount++;
const swapPair = { i: 0, j: i };
sortSteps.push({ array: [...currentArr], highlight: [i], swap: swapPair });
// Simulate the swap on the main state array for subsequent steps
let tempBars = [...bars];
[tempBars[0], tempBars[i]] = [tempBars[i], tempBars[0]];
bars = tempBars;
// Sift down on the remaining i-1 elements
siftDown(bars, 0, i - 1);
sortSteps.push({ array: [...bars], highlight: [], swap: [] });
}
animationSteps.push(...sortSteps);
}
// --- Main Animation Loop ---
function animate() {
if (!animationSteps || stepIndex >= animationSteps.length) {
animationState = 'FINISHED';
drawBars([]); // Final draw
document.getElementById('swapCount').textContent = swapCount;
return;
}
const currentStep = animationSteps[stepIndex];
// Update global state for the next step's drawing reference
bars = [...currentStep.array];
// Draw based on stored steps
drawBars(currentStep.highlight, currentStep.swap);
stepIndex++;
animationFrameId = requestAnimationFrame(animate);
}
function startAnimationCycle() {
if (animationFrameId) {
cancelAnimationFrame(animationFrameId);
}
// Reset state and capture all steps for the new run
setupAnimation();
stepIndex = 0;
swapCount = 0;
document.getElementById('swapCount').textContent = '0';
animationState = 'RUNNING';
animate();
}
// Initialization sequence setup (since we cannot use user input)
let arrays = [];
function initialSetup() {
initializeBars(); // Setup first random array for the first run visualization
arrays.push(bars);
startAnimationCycle();
}
initialSetup();
</script>
</body>
</html>
```