Göm meny
Gäller för: HT25

Heapsort

Nedan följer en exempelimplementation av Heapsort i Python.

Du kan läsa mer om Heapsort på Wikipedia och om den trädbaserade datastrukturen heap som algoritmen bygger på i boken av Miller & Ranum här och här. Ni bör också söka ytterligare källor via t.ex. Google.

En bra visualisering av hur in-place-versionen av Heapsort fungerar kan ni se på Youtube.

Notera att den enda funktionen som är rekursiv i exemplet nedan är sift_down och den rekursionen kan enkelt bytas ut mot en while-loop (pseudokodexemplet på Wikipedia använder t.ex. while istället för rekursion). Det är dock naturligt att använda rekursion här eftersom vi trots allt arbetar med en form av träd, dvs. en rekursiv datastruktur. I jämförelse med Quicksort och Mergesort, som är fundamentalt rekursiva algoritmer, är dock Heapsort en iterativ algoritm som använder en rekursiv datastruktur.

Med en separat heap representerad som en lista

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

def heap_push(heap, element):
    heap.insert(0, element)
    sift_down(heap, 0)


def heap_pop(heap):
    swap(heap, 0, -1)
    value = heap.pop()
    sift_down(heap, 0)
    return value


def smallest_existing_node(heap, i, j):
    if i < len(heap) and heap[i] < heap[j]:
        return i
    else:
        return j


def sift_down(heap, parent_node):
    left_child = 2 * parent_node + 1
    smallest = smallest_existing_node(heap, left_child, parent_node)
    right_child = 2 * parent_node + 2
    smallest = smallest_existing_node(heap, right_child, smallest)
    if smallest != parent_node:
        swap(heap, parent_node, smallest)
        sift_down(heap, smallest)


def swap(heap, i, j):
    heap[i], heap[j] = heap[j], heap[i]


def heapsort(lst):
    heap = []
    for e in lst:
        heap_push(heap, e)
    result = []
    while heap:
        result.append(heap_pop(heap))
    return result


if __name__ == "__main__":
    print("Without repeated values:")
    values = [9, 1, 10, 2, 8, 7, 3, 6, 4, 5]
    print(f"  - Before sorting: {values}")
    values = heapsort(values)
    print(f"  - After sorting:  {values}")

    print("\nWith repeated values:")
    values = [7, 9, 10, 4, 8, 1, 10, 1, 8, 7]
    print(f"  - Before sorting: {values}")
    values = heapsort(values)
    print(f"  - After sorting:  {values}")

Med en separat heap som en egen klass

Eftersom vi börjat titta på objektorientering kan det vara intressant att se hur vi skulle kunna implementera datastrukturen som en klass.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

class MinHeap:

    def __init__(self):
        self._container = []

    def __len__(self):
        return len(self._container)

    def push(self, element):
        self._container.insert(0, element)
        self._sift_down(0)

    def pop(self):
        self._swap(0, -1)
        value = self._container.pop()
        self._sift_down(0)
        return value

    def is_empty(self):
        return not self._container

    def _sift_down(self, parent_node):
        left_child = 2 * parent_node + 1
        smallest = self._smallest_existing_node(left_child, parent_node)
        right_child = 2 * parent_node + 2
        smallest = self._smallest_existing_node(right_child, smallest)
        if smallest != parent_node:
            self._swap(parent_node, smallest)
            self._sift_down(smallest)

    def _swap(self, i, j):
        self._container[i], self._container[j] = self._container[j], self._container[i]

    def _smallest_existing_node(self, i, j):
        if i < len(self) and self._container[i] < self._container[j]:
            return i
        else:
            return j

def heapsort(lst):
    heap = MinHeap()
    for e in lst:
        heap.push(e)
    result = []
    while not heap.is_empty():
        result.append(heap.pop())
    return result

if __name__ == "__main__":
    print("Without repeated values:")
    values = [9, 1, 10, 2, 8, 7, 3, 6, 4, 5]
    print(f"  - Before sorting: {values}")
    values = heapsort(values)
    print(f"  - After sorting:  {values}")

    print("\nWith repeated values:")
    values = [7, 9, 10, 4, 8, 1, 10, 1, 8, 7]
    print(f"  - Before sorting: {values}")
    values = heapsort(values)
    print(f"  - After sorting:  {values}")

In-place

Här gör vi om själva listan vi sorterar till en heap som ett steg på vägen. Sedan bygger vi upp den sorterade listan element för element från slutet av listan och framåt.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

def smallest_existing_node(lst, last_node, i, j):
    if i <= last_node and lst[i] > lst[j]:
        return i
    else:
        return j


def sift_down(lst, last_node, parent_node):
    left_child = 2 * parent_node + 1
    smallest = smallest_existing_node(lst, last_node, left_child, parent_node)
    right_child = 2 * parent_node + 2
    smallest = smallest_existing_node(lst, last_node, right_child, smallest)
    if smallest != parent_node:
        lst[parent_node], lst[smallest] = lst[smallest], lst[parent_node]
        sift_down(lst, last_node, smallest)


def heapify(lst):
    last_node = len(lst)-1
    last_parent = (last_node - 1) // 2
    for parent_node in range(last_parent, -1, -1):
        sift_down(lst, last_node, parent_node)


def heapsort(lst):
    last_index = len(lst) - 1
    heapify(lst)
    for last_node in range(last_index, 0, -1):
        lst[0], lst[last_node] = lst[last_node], lst[0]
        sift_down(lst, last_node-1, 0)

if __name__ == "__main__":
    print("Without repeated values:")
    values = [9, 1, 10, 2, 8, 7, 3, 6, 4, 5]
    print(f"  - Before sorting: {values}")
    heapsort(values)
    print(f"  - After sorting:  {values}")

    print("\nWith repeated values:")
    values = [7, 9, 10, 4, 8, 1, 10, 1, 8, 7]
    print(f"  - Before sorting: {values}")
    heapsort(values)
    print(f"  - After sorting:  {values}")

Kod för rapport

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

"""Kommentera koden på de markerade platserna.

SKRIV KOMMENTARERNA SOM ATT DE VORE RIKTIGA KOMMENTARER I DIN KOD.

- Skriv docstrings som följer PEP257 för varje funktion: "The docstring for a
  function or method should summarize its behavior and document its arguments,
  return value(s), side effects, exceptions raised, and restrictions on when it
  can be called (all if applicable). Optional arguments should be indicated. It
  should be documented whether keyword arguments are part of the interface.".
  Se https://peps.python.org/pep-0257/ för mer information.
- Lämna kvar existerande block-kommentarerna och skriv din kommentar under dem
  (se exempel på kurshemsidan).
- Inlinekommentarerna ska vara formulerade som hjälp till andra programmerare
  som läser koden. Skriv INTE dina kommentarer formulerade som svar på
  frågorna. Dvs. skriv inte "Syftet med villkoret är att ..." utan skriv
  kommentaren som om frågan inte funnits där.


# Tips

- För att förstå hur heapsort fungerar måste du förstå hur datastrukturen heap
  fungerar. Se kurshemsidan för referenser.
- Det kan underlätta att först förstå hur heapsort fungerar med en separat
  heap (se sidan om heapsort länkad från temauppgift 4).
- Börja med block-kommentarerna i funktionen innan ni skriver funktionens
  docstring.
- Börja med block-kommentarerna i looparna innan ni skriver kommentaren för
  loopen.
"""

def smallest_existing_node(lst, last_node, i, j):
    """Skriv docstring för funktionen."""
    # Förklara vad som händer i villkorssatsen. Vad är syftet med villkoret?
    if i <= last_node and lst[i] > lst[j]:
        return i
    else:
        return j


def sift_down(lst, last_node, parent_node):
    """Skriv docstring för funktionen."""
    # Förklara vad left_child och right_child representerar i heapen.
    left_child = 2 * parent_node + 1
    right_child = 2 * parent_node + 2
    # Beskriv syftet med anropen till smallest_existing_node. Vad har hänt med
    # variabeln smallest efter varje anrop?
    smallest = smallest_existing_node(lst, last_node, left_child, parent_node)
    smallest = smallest_existing_node(lst, last_node, right_child, smallest)
    # Kommentera villkorssatsen. Vad är syftet med villkoret? Beskriv vad det
    # innebär för algoritmen om smallest != parent_node?
    if smallest != parent_node:
        # Beskriv vad som händer i listan lst efter denna rad.
        lst[parent_node], lst[smallest] = lst[smallest], lst[parent_node]
        # Beskriv syftet med det rekursiva anropet till sift_down. Vad kommer ha
        # hänt i lst efter anropet?
        sift_down(lst, last_node, smallest)


def heapify(lst):
    """Skriv docstring för funktionen."""
    # Beskriv vad last_node och last_parent representerar i heapen.
    last_node = len(lst)-1
    last_parent = (last_node - 1) // 2
    # Kommentera for-loopen. Vad är syftet med loopen (vad har hänt när
    # loopen är klar)? Vad händer varje varv?
    for parent_node in range(last_parent, -1, -1):
        sift_down(lst, last_node, parent_node)


def heapsort(lst):
    """Skriv docstring för funktionen."""
    last_index = len(lst) - 1
    # Beskriv syftet med anropet till heapify. Vad har hänt i lst efter att
    # heapify har körts?
    heapify(lst)
    # Kommentera for-loopen. Vad är syftet med loopen (vad har hänt när
    # loopen är klar)? Vad händer varje varv?
    for last_node in range(last_index, 0, -1):
        lst[0], lst[last_node] = lst[last_node], lst[0]
        sift_down(lst, last_node-1, 0)

Sidansvarig: Johan Falkenjack
Senast uppdaterad: 2025-10-19