Как создать кучу?

Question

Предположим, у меня есть куча, например:

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55

Теперь я хочу вставить еще один элемент 55 в эту кучу.

Как это сделать?

Вариант 1.

         77
        /  \
       /    \
      55    60
     / \    / \
    50 30  44 55
   /
  22

Вариант 2.

     77
    /  \
   /    \
  55    60
 / \    / \
22 50  44 55
     \
     30

Вариант 3.

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  55 55
      /
     44

Какой правильный шаг?И Why?Пожалуйста, объясните.

Answer 1

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

Ваше начальное дерево

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55

Теперь добавляем 55 в соответствии с правилом на левой стороне.

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55
/
55

Но вы видите, что 22 ниже, чем 55, поэтому заменили его.

       77
      /  \
     /    \
    50    60
   / \    / \
  55 30  44 55
 /
22 

Теперь 55 стал ребенком 50, который все еще ниже 55, поэтому замените его тоже.

       77
      /  \
     /    \
    55    60
   / \    / \
  50 30  44 55
 /
22

Теперь его нельзя отсортировать больше, потому что 77 больше 55 ... Так что ваш вариант 1 правильный.

здесь вы можете увидеть пример сортировки кучи подробно .. Эта ссылка гласит куча - это специализированная древовидная структура данных, которая удовлетворяет свойству кучи: если B является дочерним узлом A, то key (A) ≥ key (B). Это означает, что элемент с наибольшим ключом всегда находится в корневом узле, и поэтому такую ​​кучу иногда называют max-heap. (В качестве альтернативы, если сравнение обращено, наименьший элемент всегда находится в корневом узле, что приводит к минимальной куче.) Нет ограничений в отношении того, сколько дочерних элементов имеет каждый узел в куче, хотя на практике каждый узел имеет максимум два.

Удачи

Answer 2

Вариант 1, по определению форма двоичной кучи - это полное двоичное дерево. Другие 2 не являются полными двоичными деревьями. Смотри http://en.wikipedia.org/wiki/Binary_heap

Answer 3

Правильный вариант - 1.

Почему?

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

В вариантах 2 и 3 элемент не вставляется как можно левее, и, следовательно, свойство полного двоичного дерева нарушается.

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

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55


       77
      /  \
     /    \
    50    60
   / \    / \
  22 30  44 55
 /
55


       77
      /  \
     /    \
    50    60
   / \    / \
  55 30  44 55
 /
22


       77
      /  \
     /    \
    55    60
   / \    / \
  50 30  44 55
 /
22

Надеюсь, это будет полезно.