![](https://habrastorage.org/files/0a5/6fb/6be/0a56fb6bec21413e9328b33cf511ea87.png)
Конечно, можно быть успешным программистом и без сакрального знания структур данных, однако они совершенно незаменимы в некоторых приложениях. Например, когда нужно вычислить кратчайший путь между двумя точками на карте, или найти имя в телефонной книжке, содержащей, скажем, миллион записей. Не говоря уже о том, что структуры данных постоянно используются в спортивном программировании. Рассмотрим некоторые из них более подробно.
Очередь
Итак, поздоровайтесь с Лупи!
![](https://habrastorage.org/files/df8/1df/761/df81df761d31451e940df9d1f16e05c7.png)
Лупи обожает играть в хоккей со своей семьей. И под “игрой”, я подразумеваю:
![](https://habrastorage.org/files/991/734/6ec/9917346ec98a495dbfa7ef1111da1c64.png)
Когда черепашки залетают в ворота, их выбрасывает на верх стопки. Заметьте, первая черепашка, добавленная в стопку — первой ее покидает. Это называется Очередь. Так же, как и в тех очередях, что мы видим в повседневной жизни, первый добавленный в список элемент — первым его покидает. Еще эту структуру называют FIFO (First In First Out).
Как насчет операций вставки и удаления?
q = []
def insert(elem):
q.append(elem) #добавляем элемент в конец очереди
print q
def delete():
q.pop(0) #удаляем нулевой элемент из очереди
print q
Стек
После такой веселой игры в хоккей, Лупи делает для всех блинчики. Она кладет их в одну стопку.
![](https://habrastorage.org/files/589/0f4/c54/5890f4c54ba9433fb49d2010d5dff5b0.png)
Когда все блинчики готовы, Лупи подает их всей семье, один за одним.
![](https://habrastorage.org/files/42d/2b7/4f6/42d2b74f668d4ce493fb42eaf1058cf8.png)
Заметьте, что первый сделанный ею блинчик — будет подан последним. Это называется Стек. Последний элемент, добавленный в список — покинет его первым. Также эту структуру данных называют LIFO (Last In First Out).
Добавление и удаление элементов?
s = []
def push(elem): #Добавление элемента в стек - Пуш
s.append(elem)
print s
def customPop(): #удаление элемента из стека - Поп
s.pop(len(s)-1)
print s
Куча
Вы когда-нибудь видели башню плотности?
![](https://habrastorage.org/files/513/cf3/bf7/513cf3bf74064a59b4103959644ada80.png)
Все элементы сверху донизу расположились по своим местам, согласно их плотности. Что случится, если бросить внутрь новый объект?
![](https://habrastorage.org/files/2fb/ee4/029/2fbee4029d074cd6bff0886f6a4ee648.gif)
Он займет место, в зависимости от своей плотности.
Примерно так работает Куча.
![](https://habrastorage.org/files/d4f/b56/cc4/d4fb56cc45ad4f7abe9bf8ba90a56401.png)
Куча — двоичное дерево. А это значит, что каждый родительский элемент имеет два дочерних. И хотя мы называем эту структуру данных кучей, но выражается она через обычный массив.
Также куча всегда имеет высоту logn, где n — количество элементов
На рисунке представлена куча типа max-heap, основанная на следующем правиле: дочерние элементы меньше родительского. Существуют также кучи min-heap, где дочерние элементы всегда больше родительского.
Несколько простых функций для работы с кучами:
global heap
global currSize
def parent(i): #Получить индекс родителя для i-того элемента
return i/2
def left(i): #Получить левый дочерний элемент от i-того
return 2*i
def right(i): #Получить правый дочерний элемент от i-того
return (2*i + 1)
Добавление элемента в существующую кучу
Для начала, мы добавляем элемент в самый низ кучи, т.е. в конец массива. Затем мы меняем его местами с родительским элементом до тех пор, пока он не встанет на свое место.
![](https://habrastorage.org/files/58a/795/3e9/58a7953e9c704b5d86c848f669de9d4e.jpg)
Алгоритм:
- Добавляем элемент в самый низ кучи.
- Сравниваем добавленный элемент с родительским; если порядок верный — останавливаемся.
- Если нет — меняем элементы местами, и возвращаемся к предыдущему пункту.
Код:
def swap(a, b): #меняем элемент с индексом a на элемент с индексом b
temp = heap[a]
heap[a] = heap[b]
heap[b] = temp
def insert(elem):
global currSize
index = len(heap)
heap.append(elem)
currSize += 1
par = parent(index)
flag = 0
while flag != 1:
if index == 1: #Дошли до корневого элемента
flag = 1
elif heap[par] > elem: #Если индекс корневого элемента больше индекса нашего элемента - наш элемент на своем месте
flag = 1
else: #Меняем местами родительский элемент с нашим
swap(par, index)
index = par
par = parent(index)
print heap
Максимальное количество проходов цикла while равно высоте дерева, или logn, следовательно, трудоемкость алгоритма — O(logn).
Извлечение максимального элемента кучи
Первый элемент в куче — всегда максимальный, так что мы просто удалим его (предварительно запомнив), и заменим самым нижним. Затем мы приведем кучу в правильный порядок, используя функцию:
maxHeapify().
![](https://habrastorage.org/files/36d/43a/ce3/36d43ace39b246778f5817640ebb6945.jpg)
Алгоритм:
- Заменить корневой элемент самым нижним.
- Сравнить новый корневой элемент с дочерними. Если они в правильном порядке — остановиться.
- Если нет — заменить корневой элемент на одного из дочерних (меньший для min-heap, больший для max-heap), и повторить шаг 2.
Код:
def extractMax():
global currSize
if currSize != 0:
maxElem = heap[1]
heap[1] = heap[currSize] #Заменяем корневой элемент - последним
heap.pop(currSize) #Удаляем последний элемент
currSize -= 1 #Уменьшаем размер кучи
maxHeapify(1)
return maxElem
def maxHeapify(index):
global currSize
lar = index
l = left(index)
r = right(index)
#Вычисляем, какой из дочерних элементов больше; если он больше родительского - меняем местами
if l <= currSize and heap[l] > heap[lar]:
lar = l
if r <= currSize and heap[r] > heap[lar]:
lar = r
if lar != index:
swap(index, lar)
maxHeapify(lar)
И вновь максимальное количество вызовов функции maxHeapify равно высоте дерева, или logn, а значит трудоемкость алгоритма — O(logn).
Делаем кучу из любого рандомного массива
Окей, есть два пути сделать это. Первый — поочередно вставлять каждый элемент в кучу. Это просто, но совершенно неэффективно. Трудоемкость алгоритма в этом случае будет O(nlogn), т.к. функция O(logn) будет выполняться n раз.
Более эффективный способ — применить функцию maxHeapify для ‘под-кучи’, от (currSize/2) до первого элемента.
Сложность получится O(n), и доказательство этого утверждения, к сожалению, выходит за рамки данной статьи. Просто поймите, что элементы, находящиеся в части кучи от currSize/2 до currSize, не имеют потомков, и большинство образованных таким образом ‘под-куч’ будут высотой меньше, чем logn.
Код:
def buildHeap():
global currSize
for i in range(currSize/2, 0, -1): #третий агрумент в range() - шаг перебора, в данном случае определяет направление.
print heap
maxHeapify(i)
currSize = len(heap)-1
![](https://habrastorage.org/files/3e7/01f/1e5/3e701f1e513940a39d99957502e2906c.png)
Действительно, зачем это все?
Кучи нужны для реализации особого типа сортировки, называемого, как ни странно, “сортировка кучей”. В отличие от менее эффективных “сортировки вставками” и “сортировки пузырьком”, с их ужасной сложностью в O(n2), “сортировка кучей” имеет сложность O(nlogn).
Реализация до неприличия проста. Просто продолжайте последовательно извлекать из кучи максимальный (корневой) элемент, и записывайте его в массив, пока куча не опустеет.
Код:
def heapSort():
for i in range(1, len(heap)):
print heap
heap.insert(len(heap)-i, extractMax()) #вставляем максимальный элемент в конец массива
currSize = len(heap)-1
Чтобы обобщить все вышесказанное, я написала несколько строчек кода, содержащего функции для работы с кучей, а для фанатов ООП оформила все в виде класса.
Легко, не правда ли? А вот и празднующая Лупи!
![](https://habrastorage.org/files/6d7/501/85f/6d750185f3644651afc0938270c7c573.jpg)
Хеш
Лупи хочет научить своих детишек различать фигуры и цвета. Для этого она принесла домой огромное количество разноцветных фигур.
![](https://habrastorage.org/files/13b/f01/b42/13bf01b429824d73bdd0a68a1ac4c2c7.png)
Через некоторое время черепашки окончательно запутались
![](https://habrastorage.org/files/640/d71/829/640d71829f644b12b7abc97d6944b858.jpg)
Поэтому она достала еще одну игрушку, чтобы немного упростить процесс
![](https://habrastorage.org/files/dce/84a/0dc/dce84a0dc47941ce99aa37155fa1eff7.jpg)
Стало намного легче, ведь черепашки уже знали, что фигуры рассортированы по форме. А что, если мы пометим каждый столб?
![](https://habrastorage.org/files/595/5d0/6a3/5955d06a33cb4fd5aaa069ee3b44d704.png)
Черепашкам теперь нужно проверить столб с определенным номером, и выбрать из гораздо меньшего количества фигурок нужную. А если еще и для каждой комбинации формы и цвета у нас отдельный столб?
Допустим, номер столба вычисляется следующим образом:
Фиолетовый треугольник
ф+и+о+т+р+е = 22+10+16+20+18+6 = Столб 92
Красный прямоугольник
к+р+а+п+р+я = 12+18+1+17+18+33 = Столб 99
и.т.д.
Мы знаем, что 6*33 = 198 возможных комбинаций, значит нам нужно 198 столбов.
Назовем эту формулу для вычисления номера столба — Хеш-функцией.
Код:
def hashFunc(piece):
words = piece.split(" ") #разбиваем строку на слова
colour = words[0]
shape = words[1]
poleNum = 0
for i in range(0, 3):
poleNum += ord(colour[i]) - 96
poleNum += ord(shape[i]) - 96
return poleNum
(с кириллицей немного сложнее, но я оставил так для простоты. — прим.пер.)
Теперь, если нам нужно будет узнать, где хранится розовый квадрат, мы сможем вычислить:
hashFunc('розовый квадрат')
![](https://habrastorage.org/files/126/c15/cec/126c15cec83e4f0bb8265bb2fb661862.png)
Это пример хеш-таблицы, где местоположение элементов определяется хеш-функцией.
При таком подходе время, затраченное на поиск любого элемента, не зависит от количества элементов, т.е. O(1). Другими словами, время поиска в хеш-таблице — константная величина.
Ладно, но допустим мы ищем “карамельный прямоугольник” (если, конечно, цвет “карамельный” существует).
hashFunc('карамельный прямоугольник')
вернет нам 99, что совпадает с номером для красного прямоугольника. Это называется “Коллизия”. Для разрешения коллизии мы используем “Метод цепочек”, подразумевающий, что каждый столб хранит список, в котором мы ищем нужную нам запись.
Поэтому мы просто кладем карамельный прямоугольник на красный, и выбираем один из них, когда хеш-функция указывает на этот столб.
Ключ к хорошей хеш-таблице — выбрать подходящую хеш-функцию. Бесспорно, это самая важная вещь в создании хеш-таблицы, и люди тратят огромное количество времени на разработку качественных хеш-функций.
В хороших таблицах ни одна позиция не содержит более 2-3 элементов, в обратном случае, хеширование работает плохо, и нужно менять хеш-функцию.
![](https://habrastorage.org/files/d21/ac6/60b/d21ac660b5354ac8ab3170328a098073.png)
Еще раз, поиск, не зависящий от количества элементов! Мы можем использовать хеш-таблицы для всего, что имеет гигантские размеры.
Хеш-таблицы также используются для поиска строк и подстрок в больших кусках текста, используя алгоритм Рабина-Карпа или алгоритм Кнута-Морриса-Пратта, что полезно, например, для определения плагиата в научных работах.
![](https://habrastorage.org/files/43b/5e4/2ef/43b5e42eff8940ccb0660bc45ff95d33.jpeg)
На этом, думаю, можно заканчивать. В будущем я планирую рассмотреть более сложные структуры данных, например Фибоначчиеву кучу и Дерево отрезков. Надеюсь, этот неформальный гайд получился интересным и полезным.
Переведено для Хабра запертым на чердаке программистом.
Комментарии (29)
conf
29.07.2015 09:51-4Спасибо за статью.
Чтобы обобщить все вышесказанное, я написала несколько строчек кода, содержащего функции для работы с кучей, а для фанатов ООП оформила все в виде класа
Во-первых, опечатка в словекласа
Во-вторых, ссылка вроде должна вести на код, оформленный в виде класса, но ведет на все тот же список функций.
Alexeyslav
29.07.2015 10:17+1Наконец-то узнал что такое куча. Всё остальное приходилось сталкиваться и использовать. Но кучи… применимость несколько ограничена.
Кстати не сказано еще что хеш-таблицы хоть и имеют малое время на поиск данных, но в компенсацию этой характеристики плохо работают на вставку/добавление новых записей посему имеют ограниченное применение.khim
29.07.2015 11:35+11Куча — достаточно специфическая структура данных: у неё теоретически весьма неплохая сложность, но обращение к памяти весьма нерегулярное и потому она эффективна только на небольших размерах (когда она влазит в L1 кеш).
А насчёт «имеющих ограниченное применение» хеш-таблиц… вы это всерьёз или просто издеваетесь? В современном мире стоить только попытаться плюнуть — попадёшь в хеш-таблицу. Ещё до того, как плюнешь.
Когда вы пишите, скажем,
то куда, собственно, попадаетvar a = 1;
a
? Ответ: в хеш-таблицу соответствующей JavaScript-функции. А когда вы пишите
то вы оперируете, скорее всего, уже с тремя хеш-таблицами (одна — в которой хранитсяa.x = b.x;
a
иb
, ещё два — живут внутри объектовa
иb
). То же самое — в большинстве других сколько-нибудь распространённых скриптовых языках (неважно: это python, ruby или какой-нибудь lisp). Даже такие языки как C++ и Java, в некотором смысле подвержены этой участи: у них тоже для каждой функции есть хеш-таблица с переменными… в компиляторе. Когда всё «замораживается» и получается скомпилированный код эти хеш-таблицы исчезают, но если вы используете какой-нибудь guice, то часть таблиц этого рода остаются и в рантайме.
С хеш-таблицами есть другая беда: если использовать некриптостойкий хеш, то можно на коллизии нарваться, а считать криптостойкие хеши долго. Слава богу тут нам пришёл на помощь Intel: на процессорах с поддержкой AES можно посчитать aeshash за то же время, что и какой-нибудь менее «замороченный» хеш, а DoS-атаку уже не провести.
Так что с хеш-таблицами всё хорошо: с вероятностью 99% вы их используете по 100 раз на дню, только не знаете об этом.Alexeyslav
29.07.2015 14:28-4хеш-таблицы хороши когда соотношение чтение/запись сильно отличается, и когда нужно за один раз выбирать одно значение из таблицы. Большинство реальных запросов из баз данных и структур далеки от этих особенностей поскольку очень редко используют полный ключ для сопоставления записей, а для хеш-таблицы требуется исключительно полный ключ для позиционирования на конкретной записи, частичный ключ не имеет никакого смысла.
Единственное преимущество — это поиск конкретных записей по полному ключу в реально огромных базах данных, когда даже двоичный поиск в сортированном массиве не проходит по временным рамкам.khim
29.07.2015 14:59+4Мы, в общем-то, говорим об одном и том же, только смотрим на проблему с разных сторон. Вы рассматриваете разные структуры с позиций «а чего, собственно, с ними можно сделать» и приходите к выводу, что хеш-таблицы ведь почти ничего делать-то и не умеют: «поиск конкретных записей по полному ключу» и только. Я же замечаю, что эта одна-единственная операция, собственно, и нужна чуть ли не в сто раз чаще, чем все остальные, вместе взятые и в результате вы, почти наверняка, используете кучу хеш-таблиц даже не замечая этого.
Единственное преимущество — это поиск конкретных записей по полному ключу в реально огромных базах данных, когда даже двоичный поиск в сортированном массиве не проходит по временным рамкам.
Ну да. Только я не знал что десяток элементов — это теперь называется «реально огромная база данных». Начиная примерно с этой точки хеш-таблицы начинают обгонять бинарный поиск — при условии, что хеш-функция распределяет данные по бакетам равномерно.MacIn
29.07.2015 23:35-2Вы всерьез не заметили, что человек сказал о куче, а не х. таблицах:
Всё остальное приходилось сталкиваться и использовать. Но кучи… применимость несколько ограничена.
?khim
30.07.2015 01:10+1Неа. Я всерьёз заметил про что именно человек говорит:
Кстати не сказано еще что хеш-таблицы хоть и имеют малое время на поиск данных, но в компенсацию этой характеристики плохо работают на вставку/добавление новых записей посему имеют ограниченное применение.
MacIn
30.07.2015 01:42-1… и в ответе стали говорить о том, что таблицы применяются повсеместно, а не характеристиках вставки и удаления и связанных с этим ограничениями по применению, что было «ядром» высказывания. То, что хеш-таблицы применяются повсеместно (во многих областях) не вляется опровержением того, что у них есть ограничения (применение ограничено в силу характеристик). «Ограниченное применение» вовсе не означает, что структура мало где применяется.
Мне стоило написать не «Вы всерьез не заметили, что человек сказал о куче, а не х. таблицах», а "… не заметили, что человек сказал об ограниченности применения без уточнений именно о куче, а не хеш-таблицах..."
В первом сообщении сказано об ограниченном применении обоих структур, но «ограниченность» хеш-таблицы аргументирована, в отличие от кучи. Причем получается по сути трюизм — у каждой структуры есть особенности, которые ограничивают ее применение. Т.е. оспаривать фразу в целом бессмысленно — она верна в таком изложении (это трюизм), оспорить можно значимость характеристик вставки и пр., но не ссылкой на массовость применения. Указание же на ограниченность применения кучи — «голая», здесь нет аргументов, оправдывающих «ограниченность», и оспорить эту часть отсылкой к широте применения — разумный первый шаг.khim
30.07.2015 02:08+1Вы тут развели какую-то философию вокруг пары фраз. Причём дурацкую. Я же отвечал по существу: куча — действительно довольно редко применяемая структура данных. Хотя обоснованием этого факта Alexeyslav действительно не озабачивался (да и непонятно как он мог озаботится если он о том как устроена эта структура узнал из этой статьи «для начинающих») — я это сделал за него.
Вторая же фраза является трюизмом только если у вас переклинило в голове и вы забыли о том, что в русском языке слова могут иметь несколько значений. Слово ограниченный — из их числа. Оно может обозначать как окруженный, отделенный, огороженный со всех сторон, так и небольшой, умеренный, имеющий достаточно узкие пределы. В первом варианте вся фраза становится трюизмом, который обсуждать бессмысленно, тут вы правы — но это, собственно, означает, что вы её неправильно поняли. Я и все остальные люди отметившиеся в теме обсуждали именно второй вариант прочтения этой фразы, вторую часть которой я и опроверг.
Обсуждать же «ядро» высказывания после этого уже не нужно: я опроверг следствие, а значит и посылка тоже неверна (вспоминаем уроки логики: из лжи может следовать как ложь, так и истина, но из истины ложь следовать никак не может).
P.S. Уж если хотите быть занудой — то хотя бы вчитывайтесь в то, что вы пишите. И не считайте всех кругом идиотами.MacIn
30.07.2015 13:47Вторая же фраза является трюизмом только если у вас переклинило в голове и вы забыли о том, что в русском языке слова могут иметь несколько значений
Именно об этом я вам и написал — о ином смысле слова «ограниченный», применимом в этом контексте.
Обсуждать же «ядро» высказывания после этого уже не нужно: я опроверг следствие
Только в случае, если воспринимать «ограниченность применения», как это сделали вы — как «редкий», «мало где применяющийся». Что, конечно, неверно. Опровержение следствия вида «хеш-таблицы используются повсюду, вы даже не замечаете этого» не опровергает посылки — посылка не была «мало где используется».
C «Я же замечаю, что эта одна-единственная операция, собственно, и нужна чуть ли не в сто раз чаще, чем все остальные, вместе взятые» не спорю.
P.S. Уж если хотите быть занудой — то хотя бы вчитывайтесь в то, что вы пишите. И не считайте всех кругом идиотами.
Что вы, это просто ремарка «проходя мимо» по поводу вашего разговора, не более. Никаких личных оценок; не воспринимайте это как выпад против вас. Вы правы по сути, и я с вами согласен в выводах. Просто претензия вида «хеш-таблицы, в силу своих особенностей (а и б) имеют ограниченное применение» разбивается простым «любая структура имеет ограничения в силу своих особенностей. Но операция поиска — наиболее частая и нагруженная, поэтому эти ограничения несущественны»(1). И это покрывает все смыслы «ограниченное применение». В отличие от «применяется повсюду»(2). (2) лишнее при наличии (1), я только об этом — по сути с вами согласен во всем.
boeing777
29.07.2015 12:13Про сортировку кучей стоит добавить, что она не требует дополнительной памяти и применима только к структурам данных с прямым доступом. И вообще, выбор метода сортировки должен производиться индивидуально под конкретную задачу. При малых размерах эффективнее могут оказаться qsort или сортировка Шелла.
И еще про применение кучи. Помимо сортировки, можно выполнять эффективный поиск элементов по определенному условию. Например, кроме банального максимума (который является корнем в max-heap), легко найти 2-й или 3-й по величине элемент — это будут непосредственные потомки корня, ну и так далее. Также куча применяется в алгоритмах на графах.khim
29.07.2015 12:27+2Вы забыли про самое распространённое применение кучи: priority queue. Когда вам нужно выбрать N самых больших (или самых маленьких) элементов из множества, то куча — это самая подходящая структура. Обыно нужное N невелико, так что главный бич кучи (нелокальные обращения к памяти) не успевает проявиться, а зато тот факт, что не нужна дополнительная память (и, главное, что не нужно эту дополнительную память выделать и освобождать) оказывается весьма полезным.
nickolaym
29.07.2015 16:26Частичная сортировка по мотивам квиксорта тоже inplace делается.
en.cppreference.com/w/cpp/algorithm/nth_element
en.cppreference.com/w/cpp/algorithm/partial_sort
Причём, если нужно просто разбить N-элементный набор по K-ной порядковой статистике, то это выполняется за O(N). А если ещё и упорядочить первые K — то O(N*logK).
Хипсорт же — гарантировано выжрет O(N*logN) на построение кучи, а затем O(K*logN) на извлечение.khim
29.07.2015 17:43+1Ну зачем же полный хипсорт-то делать? Достаточно маленькой кучки размера K. Легко и просто. Так у вас и памяти будет O(K) и времени потребуется O(N*logK). Первое — часто важнее, так как позволяет вам не портить обрабатываемые данные (если они в памяти) и обрабатывать данные, которые в память не влазят (в том числе распределённо на многих машинах). Что же касается K-ой порядковой статистики за время O(N), то сложность алгоритма (и, соответственно константа) там такие, что на небольших K (скажем до сотни) priority queue будет быстрее.
Avitella
29.07.2015 23:54Ничего подобного. www.cplusplus.com/reference/algorithm/nth_element
P.S. Сори (коменты не читай — сразу отвечай)
FlameStorm
04.08.2015 19:16> Например, кроме банального максимума (который является корнем в max-heap), легко найти 2-й или 3-й по величине элемент — это будут непосредственные потомки корня, ну и так далее. Также куча применяется в алгоритмах на графах.
Дабы читатели не остались в заблуждении, поправлю. 2й по величине элемент действительно находится в одном из двух потомков корня. А вот третий по величине элемент — это либо оставшийся потомок корня, либо один из двух потомков 2-го по величине элемента. Согласно определению кучи.
К слову, даже в той же википедии на иллюстрации-примере кучи 3-й по величине элемент находится не на первом, а на втором уровне глубины от корня.
dyadyaSerezha
29.07.2015 14:37+41. «Не говоря уже о том, что структуры данных постоянно используются в спортивном программировании.» — самый последний повод изучать структуры данных, на мой взгляд.
2. Черепашками по воротам? Куда смотрят защитники природы и комитет против пыток животных??
3. К тем же воротам — обычная очередь в магазине была бы гораздо более наглядной аналогией. Собственно, от человеческой очереди и пошло название этой структуры.
fshp
30.07.2015 05:04Хабрахабр — не для клонов.
Лучше бы от своего имени писали, а не создавали виртуала. С НЛО шутки плохи.
А за статью спасибо.
ultrabloxx
04.08.2015 13:11На рисунке представлена куча типа max-heap, основанная на следующем правиле: дочерние элементы меньше родительского. Существуют также кучи min-heap, где дочерние элементы всегда больше родительского.
На самом деле тут есть небольшая неточность, дочерние элементы в куче ещё могут быть равны родительскому элементу, иначе было бы неинтересно, а алгоритм пирамидальной сортировки требовал бы уникальности элементов массива.
radistao
04.08.2015 13:17Также куча всегда имеет высоту logn, где n — количество элементов
IMHO, в переводе на русский более привычно использоватьlog2 n
knagaev
Жаль, что не оставили в переводе оригинальное название “It’s turtles all the way down.” – A guide to the Basics of Data Structures
На самом деле это намёк на смешной случай с Бертраном Расселом.
А в целом отличный подход к знакомству со структурами данных для младшего поколения.
Или для старшего, которое ещё не наигралось.
Zveroloff
А что за случай? Не слышал.
knagaev
Этот случай, например, приведён в книге Хокинга «Кратчайшая история времени».
===
Несколько десятилетий назад известный ученый (некоторые говорят, что это был Бертран Рассел) выступал с публичной лекцией по астрономии.
Он рассказал, что Земля обращается вокруг Солнца, а оно, в свою очередь, — вокруг центра обширной звездной системы, называемой нашей Галактикой.
В конце лекции маленькая пожилая леди, сидевшая в задних рядах, встала и заявила:
— Вы рассказывали нам здесь полную ерунду. В действительности мир — это плоская плита, покоящаяся на спине гигантской черепахи.
Улыбнувшись с чувством превосходства, ученый спросил:
— А на чем стоит черепаха?
— Вы очень умный молодой человек, очень, — ответила старая леди. — Она стоит на другой черепахе, и так дальше, до бесконечности!
===
nickolaym
В более полной версии этой истории Рассел не просто рассказал о современной космологии, но перед этим обсмеял древнюю космологию с плоской землёй, китами-слонами и черепахой: мол, древние не задали себе вопрос, на чём же стоит та черепаха. А задали бы, так и отказались бы от неё.
Тут-то старушка взяла и поправила очень умного, но слишком молодого выскочку.