Heap

Hierarkisk

En komplet binær træstruktur hvor forældrenoder altid er større (max heap) eller mindre (min heap) end deres børn.

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-egenskaben: I en max heap er hver forældrenode større end eller lig med sine børn, mens i en min heap er hver forælder mindre end eller lig med sine børn. Heaps implementeres typisk som arrays for hukommelseseffektivitet, hvor for et element på indeks i, findes venstre barn på 2i+1 og højre barn på 2i+2. Heaps er fundamentale for prioritetskøer hvor elementer med højest prioritet altid er i toppen. De bruges også i heap sort-algoritmen og i planlægning hvor opgaver med højest prioritet skal behandles først. Heaps garanterer O(log n) indsættelse og sletning mens de holder roden 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å forælderindeks
  parent(i) {
    return Math.floor((i - 1) / 2);
  }

  // Få venstre barns indeks
  leftChild(i) {
    return 2 * i + 1;
  }

  // Få højre barns indeks
  rightChild(i) {
    return 2 * i + 2;
  }

  // Byt 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 (rod)
  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

•Prioritetskøer til opgaveplanlægning
•Heap sort-algoritmen
•Finde de k største/mindste elementer
•Medianvedligeholdelse i datastrømme
•Dijkstras korteste vej-algoritme

Fordele

✓O(1) adgang til min/max element
✓O(log n) indsættelse og sletning
✓Hukommelseseffektiv array-implementering
✓Perfekt til prioritetsbaserede systemer
✓Bedre end sorterede arrays til dynamiske data

Ulemper

✗Langsom søgning efter vilkårlige elementer
✗Ingen ordning udover heap-egenskaben
✗Ikke velegnet til intervalforespørgsler
✗Mere kompleks end simple køer
✗Kræver rebalancering ved modificeringer

Eksempler fra den virkelige verden

•CPU-opgaveplanlægning med prioriteter
•Skadestue-triage på hospitaler
•Printerjob-prioritering
•E-mail spam-filtreringsscorer
•Aktiehandelsordrer i realtid

Relaterede strukturer

Priority QueueBinary HeapFibonacci HeapBinomial Heap