Created
July 28, 2019 15:21
-
-
Save dobrakmato/34b29fb94b2da7bbbbeac820c5ec552a to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class EmptyError(Exception): pass | |
| class Item: | |
| def __init__(self, value): | |
| self.value = value | |
| self.next = None | |
| def __repr__(self): return f'{self.value} -> {self.next}' | |
| class Node: | |
| def __init__(self, key, value): | |
| self.key = key | |
| self.value_list = Item(value) | |
| self.left = self.right = None | |
| def __repr__(self): | |
| return f'N({self.key}, {self.value_list})' | |
| class PriorityQueue: | |
| def __init__(self): | |
| self.root = None | |
| def add(self, key, value): | |
| if self.root is None: | |
| self.root = Node(key, value) | |
| return | |
| n = self.root | |
| while "matej": | |
| if n.key == key: | |
| # najdeme koniec zoznamu | |
| s = n.value_list | |
| while s.next is not None: | |
| s = s.next | |
| s.next = Item(value) | |
| return | |
| if key < n.key: | |
| if n.left is None: | |
| n.left = Node(key, value) | |
| return | |
| n = n.left | |
| else: # n.key < key | |
| if n.right is None: | |
| n.right = Node(key, value) | |
| return | |
| n = n.right | |
| def remove_min(self): | |
| if self.root is None: raise EmptyError() | |
| p = None | |
| n = self.root | |
| while "matej": | |
| if n.left is not None: | |
| p = n | |
| n = n.left | |
| else: | |
| if n.value_list.next is not None: # ma viac ako jednu hodnotu | |
| r = (n.key, n.value_list.value) | |
| n.value_list = n.value_list.next | |
| return r | |
| else: | |
| # odstranime seba | |
| r = (n.key, n.value_list.value) | |
| if p is None: # sme v roote | |
| self.root = self.root.right | |
| return r | |
| else: | |
| # mozeme mat este pravy podstrom | |
| if n.right is None: | |
| p.left = None | |
| else: | |
| p.left = n.right | |
| return r | |
| def min(self): | |
| if self.root is None: raise EmptyError() | |
| n = self.root | |
| while "matej": | |
| if n.left is not None: | |
| n = n.left | |
| else: | |
| return (n.key, n.value_list.value) | |
| def __len__(self): | |
| if self.root is None: return 0 | |
| def len_ll(s): | |
| if s is None: return 0 | |
| c = 1 | |
| while s.next is not None: | |
| c += 1 | |
| s = s.next | |
| return c | |
| def r(n): | |
| if n is None: return 0 | |
| return r(n.left) + r(n.right) + len_ll(n.value_list) | |
| return r(self.root) | |
| def tree_height(self): | |
| if self.root is None: | |
| return -1 | |
| def h(n): | |
| if n is None: | |
| return 0 | |
| return max(h(n.left), h(n.right)) + 1 | |
| return h(self.root) -1 # vyska roota je 0 | |
| def pq_sort(pole): | |
| pq = PriorityQueue() | |
| for key, value in pole: | |
| pq.add(key, value) | |
| for i in range(len(pole)): | |
| pole[i] = pq.remove_min() | |
| if __name__ == '__main__': | |
| pole = [(4, 'prvy'), (2, 'druhy'), (1, 3.14), (3, 444), (6, 'piaty'), (9, 'a'), (7, 23), (10, 10), (8, 8)] | |
| ## pq_sort(pole) | |
| pq = PriorityQueue() | |
| for key, value in pole: | |
| pq.add(key, value) | |
| print(pq.root) | |
| print('pocet:', len(pq)) | |
| print('vyska:', pq.tree_height()) | |
| print('min:', pq.min()) | |
| for i in range(len(pole)): | |
| pole[i] = pq.remove_min() | |
| print(pole[i], len(pq), pq.tree_height()) | |
| print(pq.remove_min()) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment