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

Question

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

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

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

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

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

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

Answer 1

Решение взято с вопроса.
по @Yunus Эрен Гузель
РЕШИТЬ:

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

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 при создании и увеличивается при каждом добавлении элемента) и использовать его для поиска следующего открытого местоположения.

Для базовых структур данных вопросы, подобные этому, Wikipedia is your friend.

Answer 3

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

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

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

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 (р, с) представляет собой функцию, которая вставках узел, содержащий значение х между р и с

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

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; 
    } 
} 

Answer 4

Это мне действительно кажется, домашнее задание вопрос & это, кажется, вы еще не сделали каких-либо R & D по своему усмотрению, прежде чем просить (извините за битными резкие слова) :)

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

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

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

Answer 5

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

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