Должна ли двоичная куча быть двоичным деревом или связанным списком?

Question

У меня есть назначение для реализации двоичной кучи.Однако я не уверен, должен ли я реализовать двоичную кучу в виде структуры данных двоичного дерева или простого двойного связанного списка.

Если я должен реализовать в виде двоичного дерева, как я должен отслеживать последниеэлемент дерева для того, чтобы вставить новый элемент?В связанном списке это было бы намного проще.

Итак, должна ли двоичная куча быть двоичным деревом?Если да, как отследить последний элемент?

Примечание. В моем назначении есть такое утверждение: Но вы будете реализовывать двоичную кучу не как массив, а как дерево.

Чтобы быть более понятным, это мой узел:

struct Word{
    char * word;
    int count;
    struct Word * parent;
    struct Word * left_child;
    struct Word * right_child;
}

Answer 1

Решение взято из вопроса.
@Yunus Eren Güzel
РЕШЕНО:

После пяти часов обучения я нашел способ реализовать кучу в качестве указателяна основе дерева.Алгоритм вставки:

insert
    node = create_a_node
    parent = get_the_last_parent
    node->parent = parent
    if parent->left==NULL
        parent->left=node
    else
        parent->right=node
end insert

get_last_parent parent,&height
    height++
    if parent->left==NULL || parent->right==NULL
        return parent;
    else
        int left_height=0,right_height=0;
        left = get_last_parent(parent->left,&left_height)
        right = get_last_parent(parent->right,&right_height)
        if left_height == right_height
            height += right_height
            return right
        else if left_height > right_height
            height += left_height
            return left
end get_last_parent

Answer 2

Бинарная куча, по определению, бинарное дерево. Одним из способов реализации этого в C является сохранение элементов дерева в массиве, где индекс массива соответствует элементу дерева (нумерация корневого узла 0, его левого дочернего элемента 1, его правого дочернего элемента 2 и т. Д.). Затем вы можете просто сохранить размер кучи (инициализируется до 0 при создании и увеличиваться при добавлении элемента) и использовать его для поиска следующего открытого местоположения.

По таким вопросам, связанным с основными структурами данных, Википедия - ваш друг .

Answer 3

Проще говоря, относительно вашего первого вопроса - нет.Куча может быть чем угодно (массив, связанный список, дерево и когда нужно импровизировать семью пушистых котят).Обратите внимание на определение кучи: если «B» является потомком «A», то val (A)> = val (B) (или, в случае минимальной кучи, val (A) <= val (B)).Чаще всего его называют деревом (а также реализуют его как таковой), потому что его легко представить как дерево.Кроме того, сложность и производительность по времени хороши. </p>

Относительно вашего второго вопроса, вы не дали никакой информации, поэтому, насколько мне известно, решение, которое ищет каждый узел, так же хорошо, как и любой другой ...
Для лучшего ответа требуется больше информации (какие у вас есть ограничения, какие операции вы должны поддерживать и т. Д ...)

Answer 4

Мне кажется, это действительно домашний вопрос, и кажется, что вы сами не делали НИОКР, прежде чем спросить (извините за немного резкие слова):)

В информатике куча - этоспециализированная древовидная структура данных, которая удовлетворяет свойству кучи: если B является дочерним узлом A, то ключ (A) ≥ ключ (B).

Я думаю, ваш учитель хочет, чтобы вы внедрили структуру данных очереди с приоритетами, и именно здесь вы говорите и о связанном списке, и о куче вместе в одном вопросе.Очередь приоритетов может быть реализована в виде кучи или связанного списка, в котором для извлечения элементов на основе приоритета необходимо поддерживать сортировку элементов в случае связанного списка, где, скажем, максимальный или минимальный элемент идет впереди в зависимости от того, реализуете ли выМаксимальная куча или минимальная куча ИЛИ приоритетная очередь может быть реализована просто как структура данных кучи.

Переходя к последней точке, где вы говорите: «Но вы реализуете двоичную кучу не как массив, а как дерево., кажется, очень не имеет значения.Пожалуйста, проверьте еще раз, что требуется, или воспроизведите точный вопрос, который был задан в вашем задании.

Answer 5

Вы должны реализовать это как дерево.Это будет легко и интересно.Куча имеет только то свойство, что любой узел имеет значение, которое меньше или равно его родительскому элементу, если это максимальная куча.В реализации массива мы накладываем еще несколько условий.Если вам нужна помощь по реализации конкретной функции, вы можете спросить ее.

Вам нужно пройти вниз, чтобы добавить новый узел

вызвать его с корнем, значение для вставки

    insert(node, x){

    if(node->value >= x)
      //insert
      if(node->left == 0)
          node->left = new Node(x);
      else if(node->right == 0)
          node->right = new Node(x);
      else if(node->left->value >= x)
         insert(node->left, x);
      else if(node->right->value >= x)
         insert(node->right, x);
      else
         //insert between node and its any one child
         insertBW(node, node->left, x);
   else  //if x is less than node value
      //insert between node and its parent
      insertBW(node->parent, node, x)
   }

insertBW (p, c) - это функция, которая вставляет узел, содержащий значение x между p и c

(я не проверял этот код, проверьте наличие ошибок)

insertBW(Node* p, Node* c, T x)
{
    Node* newnode = new Node(x);
    newNode.x = x;
    if(p == 0)  //if node c is root
    {
       newnode.left = Tree.root.left;
       Tree.root = newnode;
    }
    else
    {
       newnode.parent = p;
       newnode.child  = c;
       if(p.left == c)
       {
           p.left = newnode;
       }
       else p.right = newnode;
    }
}