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

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. 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}")

Sidansvarig: Johan Falkenjack
Senast uppdaterad: 2024-10-16