Heap

Hierarkisk

En complete binary tree struktur hvor parent nodes altid er større (max heap) eller mindre (min heap) end deres children.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(n)`
Search	`O(n)`
Insertion	`O(log n)`
Deletion	`O(log n)`

Beskrivelse

En Heap er en specialiseret træstruktur der opfylder heap property: I en max heap er hver parent node større end eller lig med sine children, mens i en min heap er hver parent mindre end eller lig med sine children. Heaps implementeres typisk som arrays for memory efficiency, hvor for et element på indeks i, findes left child på 2i+1 og right child på 2i+2. Heaps er fundamentale for priority queues hvor elementer med højest prioritet altid er i toppen. De bruges også i heap sort algoritmen og i scheduling hvor tasks med højest prioritet skal behandles først. Heaps garanterer O(log n) insertion og deletion mens de holder root som min/max element. Dette gør dem ideelle til at holde styr på ekstreme værdier i dynamiske datasæt.

Kode Eksempel

// JavaScript Min Heap implementation
class MinHeap {
  constructor() {
    this.heap = [];
  }

  // Få parent index
  parent(i) {
    return Math.floor((i - 1) / 2);
  }

  // Få left child index
  leftChild(i) {
    return 2 * i + 1;
  }

  // Få right child index
  rightChild(i) {
    return 2 * i + 2;
  }

  // Swap to elementer
  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // Indsæt element
  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  // Bubble up operation
  bubbleUp(index) {
    while (index > 0) {
      const parentIdx = this.parent(index);
      if (this.heap[parentIdx] <= this.heap[index]) break;
      this.swap(parentIdx, index);
      index = parentIdx;
    }
  }

  // Fjern minimum (root)
  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }

  // Bubble down operation
  bubbleDown(index) {
    while (true) {
      let smallest = index;
      const left = this.leftChild(index);
      const right = this.rightChild(index);

      if (left < this.heap.length && 
          this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }
      if (right < this.heap.length && 
          this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }
      if (smallest === index) break;
      
      this.swap(index, smallest);
      index = smallest;
    }
  }
}

Anvendelsesområder

•Priority queues til task scheduling
•Heap sort algoritmen
•Finding k largest/smallest elements
•Median maintenance i streams
•Dijkstra's shortest path algoritme

Fordele

✓O(1) adgang til min/max element
✓O(log n) insertion og deletion
✓Memory efficient array implementation
✓Perfekt til priority-baserede systemer
✓Bedre end sorted arrays til dynamiske data

Ulemper

✗Langsom søgning efter arbitrary elements
✗Ingen ordering udover heap property
✗Ikke velegnet til range queries
✗Mere kompleks end simple queues
✗Kræver rebalancing ved modificeringer

Eksempler fra den virkelige verden

•CPU task scheduling med prioriteter
•Hospital emergency room triage
•Printer job prioritering
•Email spam filtering scores
•Real-time stock trading orders

Relaterede strukturer

Priority QueueBinary HeapFibonacci HeapBinomial Heap