SortingVisualizer/max_heap.py at master · Juda77/SortingVisualizer · 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
#max heap class used for heap sort
# Note: I implemented this class before I learned that heap sort can be
# done in-place
class max_heap:

#automatically build max heap upon instantiation
  def __init__(self, nums):

    self.heap = [] #declare an attribute
    self.build_heap(nums)
    self.heap_sort()

  def heapify_up(self, num):

    self.heap.append(num)
    curr_index = len(self.heap) - 1
    parent_index = int((curr_index - 1) / 2)
    parent = self.heap[parent_index]

    while (curr_index > 0 and parent < num):
      self.heap[parent_index] = num
      self.heap[curr_index] = parent
      curr_index = parent_index
      parent_index = int((curr_index - 1) / 2)
      parent = self.heap[parent_index]

  #takes an array of nums as input and builds a heap out of its elements
  #O(n)
  def build_heap(self, nums):

    for i in range(len(nums)):
      self.heapify_up(nums[i])

  #swap curr element and child with each other
  def swap(self, num, curr_index, child_index):

    child = self.heap[child_index]
    self.heap[curr_index] = child
    self.heap[child_index] = num

  #heapify function used as a helper for heap_sort
  def heapify_down(self, heap_size):

    curr_index = 0
    num = self.heap[curr_index]
    left_child_index = curr_index * 2 + 1
    right_child_index = curr_index * 2 + 2
    num_is_smaller_than_left = (left_child_index < heap_size and num < self.heap[left_child_index])
    num_is_smaller_than_right = (right_child_index < heap_size and num < self.heap[right_child_index])
    num_is_smaller_than_a_child = num_is_smaller_than_left or num_is_smaller_than_right

    while (num_is_smaller_than_a_child):

      #determine the bigger child
      #currently it's guaranteed that one child is bigger
      if (left_child_index >= heap_size): #if left child is not a viable option(it's out of bounds)
        self.swap(num, curr_index, right_child_index)
        curr_index = right_child_index
      elif (right_child_index >= heap_size): #if right child is not a viable option(it's out of bounds)
        self.swap(num, curr_index, left_child_index)
        curr_index = left_child_index
      else: #both children are possible options

        left = self.heap[left_child_index]
        right = self.heap[right_child_index]

        if (left >= right):
          self.swap(num, curr_index, left_child_index)
          curr_index = left_child_index
        elif (right > left):
          self.swap(num, curr_index, right_child_index)
          curr_index = right_child_index

      left_child_index = curr_index * 2 + 1
      right_child_index = curr_index * 2 + 2
      num_is_smaller_than_left = (left_child_index < heap_size and num < self.heap[left_child_index])
      num_is_smaller_than_right = (right_child_index < heap_size and num < self.heap[right_child_index])
      num_is_smaller_than_a_child = num_is_smaller_than_left or num_is_smaller_than_right

  def heap_sort(self):

    for i in range(len(self.heap), 0, -1):
      curr_max = self.heap[0]
      curr_bottom = self.heap[i - 1]
      self.heap[0] = curr_bottom
      self.heap[i - 1] = curr_max
      self.heapify_down(i - 1)
    print(self.heap)