Реализация кучи с нуля

Question

Я пытаюсь реализовать структуру данных кучи с нуля. Может ли кто-нибудь дать мне псевдокод для того же самого?

Я пытаюсь сделать каждый узел с 4 переменными. 1-я переменная для данных, 2-я переменная для родительского узла, а последние две переменные для дочерних узлов. Я знаю, что в теории узлы добавляются слева направо, но как реализовать то же самое. На данный момент я застрял в функции добавления.

class Node:
    def __init__(self,data,parent=None,child1=None,child2=None):
        self.data=data
        self.parent=parent
        self.child1=child1
        self.child2=child2

class Heap:

    def __init__(self,parent=None):
        self.parent=parent


    def add(self,data):

        new_node= Node(self,data,parent=None,child1=None,child2=None)
        new_node.parent=self.parent
        if self.parent is not none:
            if self.parent.child1 is None:
                self.parent.child1=new_node
            if self.parent.child2 is None:
                self.parent.child2=new_node
                #update self.parent=new_node??

Answer 1

Правила вставки в минимальную кучу:

add new item to the end of the array
while the new item is larger than its parent
    swap the new item with its parent

Правила удаления верхнего элемента в куче (т.е. самого маленького)

save the top item
move the last item in the array to the first position
while the item is larger than either of its children
    swap the item with its smallest child