![](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)
На этом, думаю, можно заканчивать. В будущем я планирую рассмотреть более сложные структуры данных, например Фибоначчиеву кучу и Дерево отрезков. Надеюсь, этот неформальный гайд получился интересным и полезным.
Переведено для Хабра запертым на чердаке программистом.