Code: Alles auswählen
from math import *
import random
class SortTree:
#constructor
def init(self, unsorted_list):
self.list = unsorted_list
#exchange operation
def ExchangeNode(self, i, j):
self.list[i], self.list[j] = self.list[i], self.list[j]
#iterativ nach Robert Sedgewick
def SinkNode(self, index):
max_index = len(self.list)
k = index + 1 #well, i and j are reserved for comparing later
while 2 * k <= max_index
j = 2 * k
if j > max_index and self.list[j - 1] < self.list[j]:
j += 1
if (self.list[k - 1] >= self.list[j - 1]):
break
self.ExchangeNode(k - 1, j - 1)
k=j
def get_highest_node(self):
a = self.list[0]
self.ExchangeNode(0; -1)
del self.list[-1]
self.SinkNode(0)
return "a"
unsorted = [2992, 6776, 8185, 8537, 9369, 5980, 8941, 2930, 7567, 1454,\
2932, 5568, 2599, 3127, 4101, 3621, 6252, 2369, 6410, 4259,\
3759, 1811, 4820, 5861, 5526, 4224, 7607, 7537, 1796, 193)
#create new object
my_tree = SortTree(unsorted)
print ("My unsorted list: ", my_tree.list)
#build a heap, let sink new nodes
for i in range(len(my_tree.list) - 1, -1, -1):
my_tree.SinkNode(i)
# create the new sorted list
output = [my_tree.get_highest_node() for i in range(len(my_tree.list))]
output.reverse() #yes, that’s right so
print ("\nMy sorted list: " + output)
linkes Kind des linken Kinds der Wurzel, In dieser Baumdarstellung ist das (2*x + 1)-te Listenelement das linke Kind von dem (x+1)-ten Listenelement und das (2*x + 2)-te Listenelement ist das rechte Kind von dem (x+1)-ten Listenelement.
Bei einem Max-Heap (das ist die Form von Heap die wir hier betrachten) sind die Kinder immer kleiner als der Elternknoten, wenn der Heap sich in repariertem Zustand befindet. D.h. dass die Wurzel der größte Knoten ist. Es gibt hierfür eine delete_max Operation. Die delete_max Operation entfernt das 0.te Element der Liste, also die Wurzel im Baum und fügt an den 0.ten Listenplatz dafür das letzte Listenelement. Die Funktion get_highest_node() soll also nicht den größten Knoten suchen, sondern einfach nur das 0.te Element der Liste entfernen. Das 0.te Element der Liste ist aber das größte Element sofern der Heap repariert ist.
Wie kann ich "k" hier einfügen, ohne dass der Code abschmiert. Ich habe versucht k in die def SinkNode (self, index, k) zu schreiben und self.k = k zu definieren, aber es funktioniert nicht.
Meine Korrektor soweit:
Code: Alles auswählen
"""This programm models the heap representation after Robert Sedgewick"""
import random
# Line 1: The wrong import has been removed.
class SortTree:
name = " "
# Line 5: The name attribute was. added.
# Line 5: The unnecessary commentary has been removed.
def _init_(self, unsorted_list):
# Line 6: The format of the __init__- order was corrected.
self.list = unsorted_list
# Line 7: The line was intended.
# The Operation is exchanged.
# Line 9: The sentence has ben completeted.
def ExchangeNode(self, i, j, k):
self.list[i], self.list[j] = self.list[i], self.list[j]
self.list[k] = self.list[k]
# The Iterative Method of Robert Sergewick is used.
# Line 13: The commentary has been translated to English.
def SinkNode(self, k, index):
self.index = index
self.k = k
# Line 14: Index has been defined.
max_index = len(self.list)
# Line 15: The line was inteded.
k = index + 1
# Line 16: The commentary was collequial and unnecessary.
self.k = k
while 2 * k <= max_index:
# Line 18:: A colon at the end is added.
j = 2 * k
if j > max_index and self.list[j - 1] < self.list[j]:
j += 1
if (self.list[k - 1] >= self.list[j - 1]):
break
self.ExchangeNode(k - 1, j - 1)
k=j
def get_highest_node(self):
a = self.list[0]
# Line 28: The line was intended.
self.ExchangeNode(0, -1)
# Line 29: The semicolon was replaced with a collar ,.
del self.list[-1]
self.SinkNode(0)
return "a"
unsorted = [2992, 6776, 8185, 8537, 9369, 5980, 8941, 2930, 7567, 1454,\
2932, 5568, 2599, 3127, 4101, 3621, 6252, 2369, 6410, 4259,\
3759, 1811, 4820, 5861, 5526, 4224, 7607, 7537, 1796, 193]
# Line 36: The round bracket was replaced with a square bracket.
# A new object is created
# Line 38: The sentence was completed and a space tab added.
my_tree = sort_tree(unsorted)
# Line 39: Camel Cases were replaced with underline.
print ("My unsorted list: ", my_tree.list)
#build a heap, let sink new nodes
for i in range(len(my_tree.list) - 1, -1, -1):
my_tree.SinkNode(i)
# create the new sorted list
output = [my_tree.get_highest_node() for i in range(len(my_tree.list))]
output.reverse() #yes, that’s right so
print ("\nMy sorted list: " + output)
def main():
"""This programm models the heap representation after Robobert Sedgewick."""
if __name__ == '__main__':
main()