HEAP структура на языке Swift

Структура данных heap data structure была впервые введена Дж. У. Уильямсом в 1964 г. в качестве структуры данных для алгоритма сортировки по методу heapsort.

Теоретически heap напоминает структуру данных двоичного дерева (аналогично дереву двоичного поиска). Heap - это дерево, и все узлы в дереве имеют 0, 1 или 2 детей.

Элементы в heap сортируются частями по их приоритету. Каждый узел в дереве имеет более высокий приоритет, чем его дочерние элементы. Существует два разных способа представления значений приоритетов:

• •    maxheaps: Элементы с более высоким значением представляют более высокий приоритет.

• •    minheaps: Элементы с более низким значением представляют более высокий приоритет.

Heap также имеет ограниченную высоту, делится уровни.

2ND LEVEL

3RD LEVEL

Рис.1. Уровни heap-дерева

Удаление элемента с наивысшим приоритетом

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

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

Теперь новый корневой узел - это узел с наивысшим приоритетом в дереве, но heap-дерево может быть еще не до конца отсортировано. Новый дочерний узел снова сравнивается со всеми дочерними элементами и заменяется дочерним с наивысшим приоритетом.

Сортировка продолжается, пока прежний последний элемент не будет иметь более высокий приоритет, чем его дети, или он станет листовым узлом. Так как каждый узел снова имеет более высокий приоритет, чем его дочерние элементы, heap качество дерева восстанавливается.

>

Рис.2. Удаление элемента с наивысшим приоритетом

Добавление нового элемента

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

Затем сравнивается приоритет нового элемента с его родителем, и если он имеет более высокий приоритет, то они меняются местами.

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

v* 2/ ® ® CD

----> ®

Рис.3. Добавление нового элемента

Практическое представительство

На практике структура данных heap-дерева является массивом. Каждому узлу в heap-дереве присваивается индекс. Корневому узлу начнется назначение 0, затем вниз по уровням подсчитывается индекс каждого узла слева направо.

Если бы использовались эти индексы для создания массива, каждый элемент, хранящийся в его индексированной позиции, выглядел бы так:

I [ 8,    7,5,   6,3,2,1, 4 ]

1ST 2ND 3RD 4TH

LEVEL LEVEL LEVEL LEVEL

Рис.4. Индексация позиций для массива

Каждый уровень дерева имеет в два раза больше узлов, чем уровень выше.

Учитывая узел в индексе i, его левый дочерний узел можно найти в индексе 2i + 1, а его правый дочерний узел можно найти в индексе 2i + 2.

( 8, 7, 5, 6, 3, 2, 1, 4 ]

1СЛ b.l.l

L._____J

1№ИГ U.l.l

I______________________I ICHJi.l.J

*                   *

UH ЁИ*9

Рис.5. Поиск индекса

Вот почему для heap-дерева важно быть компактным и почему каждый новый элемент добавляется в крайнее левое положение: фактически новые элементы добавляются в массив, а пробелы недопустимы.

Реализация heap-дерева на языке Swift

Создадим структуру данных:

struct Heap { var elements : [Element]

let priorityFunction : (Element, Element) -> Bool

// TODO: priority queue functions

// TODO: helper functions

}

Данная структура является generiс : она может содержать данные любого класса. У heap-дерева есть два свойства: массив элементов типа Element и функция приоритета. Функция принимает 2 Element’а и возвращает true , если первый из них имеет больший приоритет. Далее будут описаны функции для работы с heap-деревом.

Добавим следующие вычисляемые переменные в структуру:

var isEmpty : Bool { return elements.isEmpty

}

Heap-дерево пусто, если массив элементов, входящих в неё, пуст, а количество элементов равно количеству элементов массива.

Добавим функцию, которая возвращает корневое значение дерева, если оно существует. Последнее условие обозначает необходимость вернуть опциональное значение: этого элемента может и не быть.

Затем добавим функции для работы с индексами: поиском родителей элемента с заданным индексом, его детей и так далее.

func isRoot(_ index: Int) -> Bool { return (index == 0)

} func leftChildIndex(of index: Int) -> Int { return (2 * index) + 1

} func rightChildIndex(of index: Int) -> Int { return (2 * index) + 2

} func parentIndex(of index: Int) -> Int { return (index - 1) / 2

}

Необходимо отметить, что данные формулы не привязаны к самому heap-дереву: они лишь возвращают индексы элементов. Например, мы можем получить значение индекса для левого ребенка элемента с индексом 9, в то время как в самой куче 7 элементов.

Сравнение приоритетов

В теоретической части сравнение элементов с родителями и детьми использовалось широко. Реализуем эти функции.

Данная функция возвращает true, если элемент с первым индексом имеет больший приоритет. Эта функция является оболочкой для функции приоритета.

func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool { return priorityFunction(elements[firstIndex], elements[secondIndex]) }

else { return parentIndex } return childIndex }

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

func highestPriorityIndex(for parent: Int) -> Int { return highestPriorityIndex(of: highestPriorityIndex(of: parent, and: leftChildIndex(of: parent)), and: rightChildIndex(of: parent)) }

}

Добавление нового элемента

С использованием рассмотренных ранее функций-помощников дальнейшие функции будут реализовываться намного проще. Создадим функцию, которая добавляет элемент на последнее место в heap-дереве, а затем просеивает его.

siftUp(elementAtIndex: count - 1)

} mutating func siftUp(elementAtIndex index: Int) { let parent = parentIndex(of: index)

guard !isRoot(index), isHigherPriority(at: index, than: parent)

else { return } swapElement(at: index, with: parent) siftUp(elementAtIndex: parent) }

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

Удаление элемента с высшим приоритетом mutating func dequeue() -> Element? { guard !isEmpty else { return nil } swapElement(at: 0, with: count - 1)

let element = elements.removeLast()

if !isEmpty { siftDown(elementAtIndex: 0)

} return element }

Введем проверку, что heap-дерево содержит элементы. Если это условие выполняется – меняем первый и последний элемент местами и удаляем последний, сохраняя его значение в локальной переменной. Если дерево все еще содержит элементы – перемещаем первый элемент на последнее место: там, где он и находился. Функция возвращает удаленный элемент.

mutating func siftDown(elementAtIndex index: Int) { let childIndex = highestPriorityIndex(for: index)

if index == childIndex { return

} swapElement(at: index, with: childIndex)

siftDown(elementAtIndex: childIndex)

}

Принцип работы функции схож с siftUp .

Инициализация heap

Так как heap-дерево – структура, она должна иметь инициализатор, которые будет учитывать, что входной массив элементов необходимо преобразовать.

init(elements: [Element] = [], priorityFunction: @escaping (Element, Element) -> Bool) { self.elements = elements self.priorityFunction = priorityFunction buildHeap()

} mutating func buildHeap() { for index in (0 ..< count / 2).reversed() { siftDown(elementAtIndex: index)

}

}

Выводы

В рамках работы был проведен анализ heap структуры, выявлены основные преимущества данного метода хранения данных, а также структура была реализована на языке программирования Swift. Структура является простой в реализации и может быть полезна при разработке программного обеспечения. В будущем она может включаться в проекты, быть дополнена или добавлена в сам язык, являющийся open-source проектом.