Visualizations/SortingVisualizations/HeapSort.py at main · Emc2356/Visualizations · GitHub

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
from _thread import start_new_thread
import pygame
import random
import time
import sys


class Visualization:
    def __init__(self) -> None:
        pygame.event.set_allowed([pygame.QUIT, pygame.KEYDOWN])
        self.W: int = 750
        self.H: int = 750
        self.WIN: pygame.surface.Surface = pygame.display.set_mode((self.W, self.H))

        self.running: bool = True
        self.clock: pygame.time.Clock = pygame.time.Clock()
        self.FPS: int = 60

        self.i: int = 0
        self.j: int = 0
        self.array: list = []
        self.resetting = True
        self.reset()

        pygame.display.set_caption("Heap Sort")

    def reset(self) -> None:
        self.resetting = True
        time.sleep(0.5)
        self.resetting = False
        self.array = [i for i in range(1, self.W + 1)]
        random.shuffle(self.array)
        self.i = 0
        self.j = 0
        start_new_thread(self.heap_sort, ())

    def heapify(self, n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2

        if l < n and self.array[largest] < self.array[l]:
            largest = l

        if r < n and self.array[largest] < self.array[r]:
            largest = r

        if largest != i:
            self.array[i], self.array[largest] = (
                self.array[largest],
                self.array[i],
            )  # swap

            # Heapify the root.
            self.heapify(n, largest)
        time.sleep(0.001)

    def heap_sort(self):
        n = len(self.array)

        for i in range(n // 2 - 1, -1, -1):
            self.heapify(n, i)

        for i in range(n - 1, 0, -1):
            self.array[i], self.array[0] = self.array[0], self.array[i]  # swap
            self.heapify(i, 0)

    def swap(self, a: int, b: int) -> None:
        self.array[a], self.array[b] = self.array[b], self.array[a]
        time.sleep(0.001)

    def draw(self) -> None:
        self.WIN.fill((0, 0, 0))
        for x, height in enumerate(self.array):
            pygame.draw.line(
                self.WIN, (255, 255, 255), (x, self.H), (x, self.H - height), 1
            )
        pygame.display.update()

    def event_handler(self) -> None:
        mods = pygame.key.get_mods()
        for event in pygame.event.get():
            if event.type == pygame.QUIT or (
                event.type == pygame.KEYDOWN and event.key == pygame.K_ESCAPE
            ):
                pygame.quit()
                sys.exit()
            if event.type == pygame.KEYDOWN:
                if event.key == pygame.K_r and (mods & pygame.K_LCTRL):
                    self.reset()

    def run(self) -> None:
        while self.running:
            self.clock.tick(self.FPS)
            self.event_handler()
            self.draw()


def run() -> None:
    pygame.init()
    vis = Visualization()
    vis.run()


if __name__ == "__main__":
    run()