Можно ли сделать эффективные реализации двоичной кучи на основе указателей?

Можно ли реализовать двоичную кучу, используя указатели, а не массив? Я искал по всему интернету (в том числе SO) и не могу найти ответ.

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

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

Источник

6 ответов

Решение 1: сохранить указатель на последний узел

При таком подходе указатель на последний узел сохраняется, и требуются родительские указатели.

  • При вставке, начиная с последнего узла, перейдите к узлу, ниже которого будет вставлен новый последний узел. Вставьте новый узел и запомните его как последний узел. Переместите его в кучу по мере необходимости.

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

Можно перейти к упомянутым узлам в O(log(n)) времени и O(1) пространстве. Вот описание алгоритмов, но код доступен ниже:

  • Для вставки: если последний узел является левым дочерним элементом, продолжите вставку нового узла в качестве правого дочернего элемента родительского элемента. В противном случае... Начните с последнего узла. Двигайтесь вверх, пока текущий узел является правым дочерним элементом. Если корень не был достигнут, перейдите к узлу-брату справа (который обязательно существует). Затем (независимо от того, был ли достигнут корень), двигайтесь вниз влево как можно дольше. Продолжите, вставив новый узел в качестве левого потомка текущего узла.

  • Для удаления: Если последний узел является корневым, продолжите удаление корневого узла. В противном случае... Начните с последнего узла. Двигайтесь вверх, пока текущий узел является левым потомком. Если корень не был достигнут, перейдите к левому узлу (который обязательно существует). Затем (независимо от того, был ли достигнут корень), двигайтесь вниз вправо как можно дольше. Мы достигли второго до последнего узла.

Тем не менее, есть некоторые вещи, которые следует соблюдать осторожность:

  • При удалении существует два особых случая: когда удаляется последний узел (отсоедините узел и изменяете указатель последнего узла) и когда удаляется второй-последний узел (не совсем особенный, но следует учитывать возможность этого). при замене удаленного узла на последний узел).

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

Я давно сделал реализацию этого. Если это кому-то поможет, вот код. Алгоритмически это должно быть правильно (также было подвергнуто стресс-тестированию с проверкой), но, конечно, нет никаких гарантий.

Решение 2. Достигните последнего узла от корня

Это решение требует поддержания количества узлов (но не родительских указателей или последнего узла). Последний (или второй-последний) узел определяется путем перехода от корня к нему.

Предположим, что узлы пронумерованы, начиная с 1, согласно типичной записи для двоичных куч. Выберите любой действительный номер узла и представьте его в двоичном виде. Игнорировать первый (самый значимый) 1 бит. Остальные биты определяют путь от корня к этому узлу; ноль означает левый и один означает правый.

Например, чтобы добраться до узла 11 (=1011b), начните с корня, затем идите влево (0), вправо (1), вправо (1).

Этот алгоритм может использоваться во вставке, чтобы найти, где разместить новый узел (следуйте по пути для узла node_count+1), и в удалении, чтобы найти второй до последнего узла (следуйте по пути для узла node_count-1).

Этот подход используется в libuv для управления таймером; увидеть их реализацию двоичной кучи.

Полезность бинарных куч на основе указателей

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

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

Стоит отметить, что в некоторых случаях ядро ​​Linux использует (на основе указателей) красно-черные деревья в качестве очереди с приоритетами, например, для планирования ЦП и управления таймером (для тех же целей, что и в libuv). Я считаю вероятным, что изменение их для использования двоичной кучи на основе указателей улучшит производительность.

Гибридный подход

Можно объединить Решение 1 и Решение 2 в гибридный подход, который динамически выбирает любой из алгоритмов (для нахождения последнего или предпоследнего узла), один с более низкой стоимостью, измеряемый числом ребер, которые нуждаются быть пройденным. Предположим, мы хотим перейти к узлу с номером N, и highest_bit(X) означает основанный на 0 индекс бита высшего порядка в N (0 означает младший бит).

  • Стоимость навигации от рута (Решение 2) составляет highest_bit(N),

  • Стоимость навигации от предыдущего узла, который находится на том же уровне (Решение 1), составляет: 2 * (1 + highest_bit((N-1) xor N)),

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

У некоторых процессоров есть инструкция для highest_bit что позволяет очень эффективно выполнять эти оценки. Альтернативный подход состоит в том, чтобы поддерживать старший бит в качестве битовой маски и выполнять эти вычисления с битовыми масками вместо битовых индексов. Рассмотрим, например, что 1, за которым следует N квадратов нулей, равно 1, за которым следуют 2N нулей).

В ходе моего тестирования выяснилось, что Решение 1 в среднем быстрее, чем Решение 2, и гибридный подход, по-видимому, имеет примерно такую ​​же среднюю производительность, что и Решение 2. Поэтому гибридный подход полезен, только если необходимо минимизировать наихудший случай. время, которое (вдвое) лучше в решении 2; поскольку решение 1 в худшем случае пройдет всю высоту дерева вверх, а затем вниз.

Код для решения 1

Обратите внимание, что код обхода во вставке немного отличается от алгоритма, описанного выше, но все еще корректен.

struct Node {
    Node *parent;
    Node *link[2];
};

struct Heap {
    Node *root;
    Node *last;
};

void init (Heap *h)
{
    h->root = NULL;
    h->last = NULL;
}

void insert (Heap *h, Node *node)
{
    // If the heap is empty, insert root node.
    if (h->root == NULL) {
        h->root = node;
        h->last = node;
        node->parent = NULL;
        node->link[0] = NULL;
        node->link[1] = NULL;
        return;
    }

    // We will be finding the node to insert below.

    // Start with the current last node and move up as long as the
    // parent exists and the current node is its right child.
    Node *cur = h->last;
    while (cur->parent != NULL && cur == cur->parent->link[1]) {
        cur = cur->parent;
    }

    if (cur->parent != NULL) {
        if (cur->parent->link[1] != NULL) {
            // The parent has a right child. Attach the new node to
            // the leftmost node of the parent's right subtree.
            cur = cur->parent->link[1];
            while (cur->link[0] != NULL) {
                cur = cur->link[0];
            }
        } else {
            // The parent has no right child. This can only happen when
            // the last node is a right child. The new node can become
            // the right child.
            cur = cur->parent;
        }
    } else {
        // We have reached the root. The new node will be at a new level,
        // the left child of the current leftmost node.
        while (cur->link[0] != NULL) {
            cur = cur->link[0];
        }
    }

    // This is the node below which we will insert. It has either no
    // children or only a left child.
    assert(cur->link[1] == NULL);

    // Insert the new node, which becomes the new last node.
    h->last = node;
    cur->link[cur->link[0] != NULL] = node;
    node->parent = cur;
    node->link[0] = NULL;
    node->link[1] = NULL;

    // Restore the heap property.
    while (node->parent != NULL && value(node->parent) > value(node)) {
        move_one_up(h, node);
    }
}

void remove (Heap *h, Node *node)
{
    // If this is the only node left, remove it.
    if (node->parent == NULL && node->link[0] == NULL && node->link[1] == NULL) {
        h->root = NULL;
        h->last = NULL;
        return;
    }

    // Locate the node before the last node.
    Node *cur = h->last;
    while (cur->parent != NULL && cur == cur->parent->link[0]) {
        cur = cur->parent;
    }
    if (cur->parent != NULL) {
        assert(cur->parent->link[0] != NULL);
        cur = cur->parent->link[0];
    }
    while (cur->link[1] != NULL) {
        cur = cur->link[1];
    }

    // Disconnect the last node.
    assert(h->last->parent != NULL);
    h->last->parent->link[h->last == h->last->parent->link[1]] = NULL;

    if (node == h->last) {
        // Deleting last, set new last.
        h->last = cur;
    } else {
        // Not deleting last, move last to node's place.
        Node *srcnode = h->last;
        replace_node(h, node, srcnode);
        // Set new last unless node=cur; in this case it stays the same.
        if (node != cur) {
            h->last = cur;
        }

        // Restore the heap property.
        if (srcnode->parent != NULL && value(srcnode) < value(srcnode->parent)) {
            do {
                move_one_up(h, srcnode);
            } while (srcnode->parent != NULL && value(srcnode) < value(srcnode->parent));
        } else {
            while (srcnode->link[0] != NULL || srcnode->link[1] != NULL) {
                bool side = srcnode->link[1] != NULL && value(srcnode->link[0]) >= value(srcnode->link[1]);
                if (value(srcnode) > value(srcnode->link[side])) {
                    move_one_up(h, srcnode->link[side]);
                } else {
                    break;
                }
            }
        }
    }
}

Используются две другие функции: move_one_up перемещает узел на один шаг вверх в куче, и replace_node Замена перемещает существующий узел (srcnode) в место, которое занимает удаляемый узел. Оба работают только путем настройки ссылок на другие узлы и из них, фактическое перемещение данных не происходит. Эти функции не должны быть сложными для реализации, и упомянутая ссылка включает мои реализации.

Источник

Реализация двоичной кучи на основе указателя невероятно сложна по сравнению с реализацией на основе массива. Но это весело, чтобы закодировать это. Основная идея - идея двоичного дерева. Но самая большая проблема, с которой вы столкнетесь, - это оставить ее заполненной. Вам будет сложно найти точное местоположение, где вы должны вставить узел.

Для этого вы должны знать бинарный обход. Что мы делаем Предположим, что наш размер кучи равен 6. Мы возьмем число + 1 и преобразуем его в биты. Двоичное представление числа 7 - "111". Теперь не забывайте всегда опускать первый бит. Итак, теперь мы остались с "11". Читайте слева направо. Бит равен 1, поэтому перейдите к правому дочернему элементу корневого узла. Тогда оставленная строка - "1", первый бит - "1". Поскольку у вас есть только 1 бит, этот единственный бит сообщает вам, куда вставить новый узел. Поскольку это '1', новый узел должен быть правым дочерним узлом текущего узла. Итак, необработанная работа процесса заключается в том, что преобразуйте размер кучи в биты. Опустить первый бит. В соответствии с крайним левым битом перейдите к правому дочернему элементу текущего узла, если он равен "1", и к левому дочернему элементу текущего узла, если он равен "0".

После вставки нового узла, вы будете раздувать его вверх по куче. Это говорит о том, что вам понадобится родительский указатель. Итак, вы идете один раз вниз по дереву и один раз вверх по дереву. Итак, ваша операция вставки займет O(log N).

Что касается удаления, то все еще сложно найти последний узел. Я надеюсь, что вы знакомы с удалением в куче, где мы меняем его местами с последним узлом и выполняем heapify. Но для этого вам нужен последний узел, для этого мы также используем ту же технику, что и для поиска места для вставки нового узла, но с небольшим поворотом. Если вы хотите найти местоположение последнего узла, вы должны использовать двоичное представление самого значения HeapSize, а не HeapSize + 1. Это приведет вас к последнему узлу. Таким образом, удаление также будет стоить вам O (журнал N).

У меня проблемы с размещением исходного кода здесь, но вы можете обратиться к моему блогу за исходным кодом. В коде также есть сортировка кучи. Это очень просто. Мы просто продолжаем удалять корневой узел. Обратитесь к моему блогу для объяснения с цифрами. Но я думаю, это объяснение подойдет.

Я надеюсь, что мой ответ помог вам. Если это так, дайте мне знать...! ☺

Источник

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

Чтобы ответить на вопрос OP, родительские указатели и / или подробное отслеживание не нужны, чтобы определить, куда вставить следующий узел или найти текущий последний. Вам нужны только биты в двоичном повторении размера кучи, чтобы определить левый и правый дочерние указатели для подражания.

Edit Только что видел объяснение Vamsi Sangam @ этого алгоритма. Тем не менее, вот демо в коде:

#include <stdio.h>
#include <stdlib.h>

typedef struct node_s {
  struct node_s *lft, *rgt;
  int data;
} NODE;

typedef struct heap_s {
  NODE *root;
  size_t size;
} HEAP;

// Add a new node at the last position of a complete binary tree.
void add(HEAP *heap, NODE *node) {
  size_t mask = 0;
  size_t size = ++heap->size;
  // Initialize the mask to the high-order 1 of the size.
  for (size_t x = size; x; x &= x - 1) mask = x;
  NODE **pp = &heap->root;
  // Advance pp right or left depending on size bits.
  while (mask >>= 1) pp = (size & mask) ? &(*pp)->rgt : &(*pp)->lft;
  *pp = node;
}   

void print(NODE *p, int indent) {
  if (!p) return;
  for (int i = 0; i < indent; i++) printf(" ");
  printf("%d\n", p->data);
  print(p->lft, indent + 1);
  print(p->rgt, indent + 1);
}   

int main(void) {
  HEAP h[1] = { NULL, 0 };
  for (int i = 0; i < 16; i++) {
    NODE *p = malloc(sizeof *p);
    p->lft = p->rgt = NULL;
    p->data = i;
    add(h, p);
  }   
  print(h->root, 0);
}

Как вы надеетесь, он печатает:

0
 1
  3
   7
    15
   8
  4
   9
   10
 2
  5
   11
   12
  6
   13
   14

Sift-down может использовать тот же вид итерации. Также возможно реализовать sift-up без родительских указателей, используя либо рекурсию, либо явный стек, чтобы "сохранить" узлы на пути от корня до просеиваемого узла.

Источник

Бинарная куча - это полное двоичное дерево, подчиняющееся свойству кучи. Это все. То, что его можно хранить с помощью массива, просто приятно и удобно. Но, конечно, вы можете реализовать это с помощью связанной структуры. Это забавное упражнение! Как таковой, он в основном полезен в качестве упражнения или в более сложных структурах данных (например, для сменных адресных очередей с приоритетом), так как он немного сложнее, чем версия массива. Например, подумайте о процедурах siftup/siftdown и обо всех способах вырезания / шитья, которые вам понадобятся, чтобы получить правильные результаты. В любом случае, это не так уж сложно, и еще раз, весело!

Источник

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

Вот в чем проблема - никогда нет причин делать это, так как использование массива лучше во всех отношениях.

Если вы выполняете поиск, пытаясь найти информацию о том, как работать с кучей, используя указатели, вы не найдете ничего - никто не будет беспокоиться, так как нет причин для реализации двоичной кучи таким образом.

Если вы выполните поиск по деревьям, вы найдете много полезных материалов. Это был смысл моего первоначального ответа. Нет ничего, что мешало бы людям делать это таким образом, но для этого никогда нет причин.

Вы говорите - я должен сделать это, у меня есть устаревшая система, и у меня есть указатели на узлы, которые мне нужны, чтобы поместить их в кучу.

Создайте массив этих указателей и работайте с ними в этом массиве, как если бы вы использовали стандартную кучу на основе массива, когда вам нужно разыменовать их содержимое. Это будет работать лучше, чем любой другой способ реализации вашей системы.

Я не могу представить себе никакой другой причины для реализации кучи с помощью указателей.

Оригинальный ответ:

Если вы реализуете его с помощью указателей, то это дерево. Куча - это куча из-за того, как вы можете вычислить местоположение дочерних элементов как местоположение в массиве (2 * индекс узла +1 и 2 * индекс узла + 2).

Так что нет, вы не можете реализовать это с помощью указателей, если вы реализовали дерево.

Реализация деревьев хорошо документирована, если вы будете искать, вы найдете ответы.

Источник

Я искал по всему интернету (в том числе SO) и не могу найти ответ.

Забавно, потому что я нашел ответ на SO в течение нескольких секунд, пытаясь найти его. (Тот же поиск Google привел меня сюда.)

В принципе:

  • Узел должен иметь указатели на своего родителя, левого потомка и правого потомка.
  • Вы должны сохранить указатели на:
    • корень дерева (root) (дух)
    • последний вставленный узел (lastNode)
    • самый левый узел самого низкого уровня (leftmostNode)
    • самый правый узел ближайшего к нижнему уровню (rightmostNode)

Теперь, пусть будет вставлен узел nodeToInsert, Алгоритм вставки в псевдокод:

void insertNode(Data data) {
    Node* parentNode, nodeToInsert = new Node(data);
    if(root == NULL) { // empty tree
        parent = NULL;
        root = nodeToInsert;
        leftmostNode = root;
        rightmostNode = NULL;
    } else if(lastNode.parent == rightmostNode && lastNode.isRightChild()) { 
        // level full
        parentNode = leftmostNode;
        leftmostNode = nodeToInsert;
        parentNode->leftChild = nodeToInsert;
        rightmostNode = lastNode;
    } else if (lastNode.isLeftChild()) {
        parentNode = lastNode->parent;
        parentNode->rightChild = nodeToInsert;
    } else if(lastNode.isRightChild()) {
        parentNode = lastNode->parent->parent->rightChild;
        parentNode->leftChild = nodeToInsert;
    }
    nodeToInsert->parent = parentNode;
    lastNode = nodeToInsert;
    heapifyUp(nodeToInsert);
}

Псевдокод для удаления:

Data deleteNode() {
    Data result = root->data;
    if(root == NULL) throw new EmptyHeapException();
    if(lastNode == root) { // the root is the only node
        free(root);
        root = NULL;
    } else {
        Node* newRoot = lastNode;
        if(lastNode == leftmostNode) {
            newRoot->parent->leftChild = NULL;
            lastNode = rightmostNode;
            rightmostNode = rightmostNode->parent;  
        } else if(lastNode.isRightChild()) {
            newRoot->parent->rightChild = NULL;
            lastNode = newRoot->parent->leftChild;
        } else if(lastNode.isLeftChild()) {
            newRoot->parent->leftChild = NULL;
            lastNode = newRoot->parent->parent->leftChild->rightChild;
        }
        newRoot->leftChild  = root->leftChild;
        newRoot->rightChild = root->rightChild;
        newRoot->parent = NULL;
        free(root);
        root = newRoot;
        heapifyDown(root);
    }
    return result;
}

heapifyUp() а также heapifyDown() не должно быть слишком сложно, хотя, конечно, вы должны убедиться, что эти функции не делают leftmostNode, rightmostNode, или же lastNode указать в неправильном месте.

TL; DR Просто используйте чертов массив.

Источник
Другие вопросы по тегам