-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge.py
127 lines (109 loc) · 3.86 KB
/
merge.py
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
from functools import partial
from bokeh.layouts import column, row
from bokeh.models import Button, ColumnDataSource, Slider
from bokeh.palettes import RdYlBu3
from bokeh.plotting import figure, curdoc
from numpy import random
import time
from bokeh.models.widgets import Select
import panel as pn
### Creating the data
from minheap import MinHeap
from functools import partial
from bokeh.layouts import column, row
from bokeh.models import Button, ColumnDataSource, Slider
from bokeh.palettes import RdYlBu3
from bokeh.plotting import figure, curdoc
from numpy import random
import time
from bokeh.models.widgets import Select
import panel as pn
size = 100
arr = random.randint(20, size=size).tolist()
index = [i for i in range(size)]
color = ['red' for _ in range(size)]
### Merge Sort Functino
def merge_sort(arr):
pass
def heap_sort(arr):
pass
### Heap implementationj
llist = []
heap = MinHeap(arr,color)
source = ColumnDataSource(dict(index=index, arr=arr, color=color))
### Visualisation basics
f = figure()
f.vbar(x='index', top='arr', fill_color='color', source=source)
removed = []
def callback():
global removed,source,heap,size
if heap.heap:
min = heap.remove()
removed.append(min)
llist = heap.heap.copy()
llist.extend(removed)
source.data['arr'] = llist
color = ['red'] * size
for i in range(len(removed)):
color[len(color)-1-i]='green'
source.data['color'] = color
# remove_flag = True
# last_index = len(heap.heap) - 1
# index = 0
# def callback_1():
# global removed, source, heap, size,remove_flag,last_index,index
# if heap.heap:
# # if remove_flag == True:
# min = heap.remove()
# removed.append(min)
# ## First I have to swap
# color = ['red'] * (size)
# heap.swap(0, len(heap.heap) - 1, heap.heap,heap.color)
# color[0] = 'blue'
# color[len(heap.heap) - 1] = 'blue'
# source.data['color'] = color
# ## Pop an element
# value = heap.heap.pop(-1)
# color[len(heap.heap) - 1] = 'blue'
# source.data['color'] = color
# removed.append(value)
# llist = heap.heap.copy()
# llist.extend(removed)
# source.data['arr'] = llist
# ## Rearrage
# # else:
# last_index = len(heap.heap) - 1
# childNodeOne = index * 2 + 1
# while childNodeOne <= last_index:
#
# childIndexTwo = index * 2 + 2 if index * 2 + 2 <= last_index else -1
# if childIndexTwo != -1 and heap.heap[childIndexTwo] < heap.heap[childNodeOne]:
# idxToSwap = childIndexTwo
# print('compare child nodes', heap.heap[childIndexTwo], heap.heap[childNodeOne])
# else:
# idxToSwap = childNodeOne
# print('swap', heap.heap[idxToSwap])
# if heap.heap[idxToSwap] < heap.heap[index]:
# color = ['red'] * (size)
# heap.swap(index, idxToSwap, heap.heap, color)
# color = ['red'] * size
# color[index] = 'blue'
# color[idxToSwap] = 'blue'
# source.data['color'] = color
# index = idxToSwap
# print('hey')
# childNodeOne = index * 2 + 1
# if childNodeOne <= last_index:
# print('update node', heap.heap[childNodeOne])
# else:
# # llist = heap.heap.copy()
# # llist.extend(removed)
# # source.data['arr'] = llist
# # remove_flag = True
# # if remove_flag:
# # print('remove', heap.heap[childNodeOne])
# # else:
# # print('update node', heap.heap[childNodeOne])
# break
curdoc().add_root(column(f))
curdoc().add_periodic_callback(callback, 1000)