Recently, the data structure is a little interesting, so I'm going to make software that visualizes the data structure little by little while also practicing OOP.
As the first step, we visualized the heap. I hope you can see it if you like. If I have a chance, I will write an article about heapsort. I will update it again.
By the way, I'm running on mac so I don't know how it works on windows.
from tkinter import *
import time
class EntryAndButton(Frame):
def __init__(self, master, **kwargs):
super().__init__(master)
self.grid(column=0, row=0, sticky=NSEW)
self.entry = Entry(self)
self.entry.grid(column=0, row=1, sticky=NSEW)
self.button = Button(self, **kwargs)
self.button.grid(column=0, row=2)
self.columnconfigure(0, weight=1)
self.rowconfigure(0, weight=1)
self.rowconfigure(1, weight=1)
self.rowconfigure(2, weight=1)
self.rowconfigure(3, weight=1)
def getVal(self):
val = self.entry.get()
self.entry.delete(0, END)
return val
class MakeToolbar(Frame):
def __init__(self, master):
super().__init__(master)
self.master = master
self.grid(row=0, column=0, sticky=NSEW)
def makeToolbar(self, toolbar):
for i, (ui, kwds) in enumerate(toolbar):
name = 'widget'+str(i)
setattr(self, name, ui(self, **kwds))
wid = getattr(self, name)
wid.grid(row=i, column=0, sticky=NSEW)
self.rowconfigure(i, weight=1)
class PicAndOpes(Frame):
def __init__(self, master=None):
super().__init__(master)
self.master = master
self.grid(column=0, row=0, sticky=NSEW)
self.master.columnconfigure(0, weight=1)
self.master.rowconfigure(0, weight=1)
self.canvas = Canvas(self, background='white')
self.canvas.grid(row=0, column=0, sticky=NSEW)
self.master.update()
self.canvas.config(width=self.canvas.winfo_width(), height=self.canvas.winfo_height())
self.operations = MakeToolbar(self)
self.operations.grid(row=0, column=1, sticky=NSEW)
self.operations.columnconfigure(0, weight=1)
self.columnconfigure(0, weight=1)
self.columnconfigure(1, weight=1)
self.rowconfigure(0, weight=1)
class Stack():
def __init__(self, master):
self.frame = PicAndOpes(master)
self.master = master
self.master.title('stack')
self.num = 0
self.size = 16
self.cor_x = self.frame.canvas.winfo_width()/2
self.cor_y = self.frame.canvas.winfo_height() - self.size
self.frame.canvas.bind('<Configure>', self.resize)
self.frame.operations.makeToolbar(((Button, {'text':'add', 'command':self.add}),(Button, {'text':'pop', 'command':self.pop}),))
def add(self):
self.num = self.num + 1
self.frame.canvas.create_rectangle(self.cor_x-self.size, self.cor_y-self.num*self.size/2, self.cor_x+self.size, self.cor_y-(self.num+1)*self.size/2, tag=('stack'+str(self.num)))
def pop(self):
self.frame.canvas.delete('stack'+str(self.num))
self.num = self.num-1
def resize(self, event):
self.frame.canvas.move('all', event.width/2-self.cor_x, event.height-self.cor_y - self.size)
self.cor_x, self.cor_y = event.width/2, event.height - self.size
class Heap():
def __init__(self, master=None):
#Heap node will be allocated from 1
#The height of heap will be allocated from 0
self.frame = PicAndOpes(master)
self.master = master
self.master.title('heap')
self.nodeNum = 0
self.rad = 10
self.gap = 15
self.edge_length = 20
self.heapHeight = 0
self.heapCurrentHeight = 0
self.top_cor_x = self.frame.canvas.winfo_width() / 2
self.top_cor_y = (self.frame.canvas.winfo_height() - 2 * self.rad * self.heapHeight) / 2
self.next_cor_x = self.frame.canvas.winfo_width()/2
self.next_cor_y = self.frame.canvas.winfo_height()/2
self.frame.canvas.bind('<Configure>', self.resize)
self.frame.operations.makeToolbar(((EntryAndButton, {'text':'append', 'command':self.append}),
(Button, {'text':'getMin', 'command':self.getMin}),
(Button, {'text':'heapify', 'command':self.heapify}))
)
def append(self):
val = self.frame.operations.widget0.getVal()
if val == "":
print('write something')
else:
self.nodeNum = self.nodeNum + 1
if 2**(self.heapHeight + 1) == (self.nodeNum):
self.heapHeight = self.heapHeight + 1
self.heapCurrentHeight = 0
self.redraw(val)
else:
self.heapCurrentHeight = self.heapHeight
self.frame.canvas.create_oval(self.next_cor_x-self.rad,
self.next_cor_y-self.rad,
self.next_cor_x+self.rad,
self.next_cor_y+self.rad,
fill='white',
tag=('shape'+str(self.nodeNum)))
self.frame.canvas.create_text(self.next_cor_x,
self.next_cor_y,
text=val, tag=('text'+str(self.nodeNum)))
self.set_next_cor(self.nodeNum)
def redraw(self, val):
self.top_cor_x = self.frame.canvas.winfo_width() / 2
self.top_cor_y = (self.frame.canvas.winfo_height() - 2 * self.rad * self.heapHeight) / 2
self.next_cor_x = self.top_cor_x
self.next_cor_y = self.top_cor_y
for i in range(1, self.nodeNum):
x0, y0, x1, y1 = self.frame.canvas.coords('shape'+str(i))
x, y = (x0+x1)/2, (y0+y1)/2
self.frame.canvas.move('shape'+str(i), self.next_cor_x-x, self.next_cor_y-y)
self.frame.canvas.move('text'+str(i), self.next_cor_x-x, self.next_cor_y-y)
self.set_next_cor(i)
self.frame.canvas.create_oval(self.next_cor_x-self.rad, self.next_cor_y-self.rad, self.next_cor_x+self.rad, self.next_cor_y+self.rad, fill='white',tag=('shape'+str(self.nodeNum)))
self.frame.canvas.create_text(self.next_cor_x, self.next_cor_y, text=val, tag=('text'+str(self.nodeNum)))
self.set_next_cor(self.nodeNum)
#set_next_i as cor finished up to the i-th node+Put the coordinates of the first node in next
def set_next_cor(self, i):
if (2**(self.heapCurrentHeight + 1) - 1 ) == i:
self.heapCurrentHeight = self.heapCurrentHeight + 1
sum = 0
for j in range(self.heapCurrentHeight):
sum = sum + 2**(self.heapHeight - j - 1)
self.next_cor_x = self.top_cor_x - self.gap * sum
self.next_cor_y = self.next_cor_y + 2 * self.gap
else:
self.next_cor_x = self.next_cor_x + 2 * self.gap * 2**(self.heapHeight - self.heapCurrentHeight)
def resize(self, event):
diffx = event.width / 2 - self.top_cor_x
diffy = (event.height - 2 * self.rad * self.heapHeight) / 2 - self.top_cor_y
self.frame.canvas.move('all', diffx, diffy)
self.top_cor_x, self.top_cor_y = event.width/2, (event.height - 2 * self.rad * self.heapHeight) / 2
self.next_cor_x, self.next_cor_y = self.next_cor_x + diffx, self.next_cor_y + diffy
def getMin(self):
if self.nodeNum == 0:
pass
elif self.nodeNum == 1:
pass
else:
parentid = self.frame.canvas.find_withtag('text' + str(1))
lastid = self.frame.canvas.find_withtag('text' + str(self.nodeNum))
last = self.frame.canvas.itemcget(lastid, 'text')
self.frame.canvas.itemconfig(parentid, text='')
time.sleep(1)
self.master.update()
self.frame.canvas.itemconfig(parentid, text=last)
self.frame.canvas.delete('shape'+str(self.nodeNum))
self.frame.canvas.delete('text'+str(self.nodeNum))
time.sleep(1)
self.master.update()
self.nodeNum = self.nodeNum - 1
self.subheapify(1)
def heapify(self):
ran = 2**self.heapHeight - 1
for i in reversed(range(1, ran + 1)):
self.subheapify(i)
def subheapify(self, i):
flag = True
max = self.nodeNum
while flag:
n = i
if max < 2*i:
flag = False
elif 2*i <= max < (2*i + 1):
parentid = self.frame.canvas.find_withtag('text' + str(n))[0]
leftchildid = self.frame.canvas.find_withtag('text' + str(2*n))[0]
parent = self.frame.canvas.itemcget(parentid, 'text')
leftchild = self.frame.canvas.itemcget(leftchildid, 'text')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(n))[0], fill='red')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(n))[0], fill='white')
time.sleep(1)
self.master.update()
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n))[0], fill='blue')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n))[0], fill='white')
time.sleep(1)
self.master.update()
if leftchild < parent:
self.frame.canvas.itemconfig(parentid, text=leftchild)
self.frame.canvas.itemconfig(leftchildid, text=parent)
time.sleep(1)
self.master.update()
i = 2 * i
elif parent <= leftchild:
flag = False
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(n))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(n))[0], fill='black')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n))[0], fill='black')
time.sleep(1)
self.master.update()
elif (2*i+1) <= max:
parentid = self.frame.canvas.find_withtag('text' + str(n))[0]
leftchildid = self.frame.canvas.find_withtag('text' + str(2*n))[0]
rightchildid = self.frame.canvas.find_withtag('text' + str(2*n+1))[0]
parent = self.frame.canvas.itemcget(parentid, 'text')
leftchild = self.frame.canvas.itemcget(leftchildid, 'text')
rightchild = self.frame.canvas.itemcget(rightchildid, 'text')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(n))[0], fill='red')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(n))[0], fill='white')
time.sleep(1)
self.master.update()
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n))[0], fill='blue')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n+1))[0], fill='blue')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n+1))[0], fill='white')
time.sleep(1)
self.master.update()
if leftchild <= rightchild:
if leftchild < parent:
self.frame.canvas.itemconfig(parentid, text=leftchild)
self.frame.canvas.itemconfig(leftchildid, text=parent)
time.sleep(1)
self.master.update()
i = 2 * i
elif parent <= leftchild:
flag = False
elif rightchild < leftchild:
if rightchild < parent:
self.frame.canvas.itemconfig(parentid, text=rightchild)
self.frame.canvas.itemconfig(rightchildid, text=parent)
time.sleep(1)
self.master.update()
i = 2 * i + 1
elif parent <= rightchild:
flag = False
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(n))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n+1))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(n))[0], fill='black')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n))[0], fill='black')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n+1))[0], fill='black')
time.sleep(1)
self.master.update()
def main():
root = Tk()
app = Heap(root)
root.mainloop()
if __name__ == '__main__':
main()