[Lecture Summary] 07 Algorithm and Data Structure : Binary Heap

This contents is based on Lecture of link

Priority Queue Interface

This is a kind of Set Interface and the difference is that key has a priority as an attribute.

Operation

As it is a set interface, we should support find operation. At the same time, there is an order of priority so operation is based on the most import item. That’s why we support max feature on some operations.

build() / insert() / delete_max() / find_max()

Priority Queue Sort

The reason why we call it as a sort algorithim is that there is an order we need to acquire. Therefore Data Structure for Priority Queue Interface can be interpreted as a sorting.

In that point, build DS for Priority Queue Sort is accompanied with sorting algorithm and that’s why build for Set AVL Tree DS takes $n\log(n)$ to make sort. However, sorting algorithm is not in-place algorithm.

Selection Sort is considered as Unsorted Dynamic Array for Priority Queue DS because we need to run sorting algorithm for unsorted items. This is just the case for Selection Sort where there exist unsorted items and sort them in-place.

Insert Sort is consider as Sorted Dynamic Array because sorting should be implemented in building and this is just the case for Insertion Sort where we can repeated insert item in sorted way and get sorted Dynamic Array!

We’d like to make DS working as Set AVL Tree with in-place sorting!

Set AVL Tree

All the operations (including find_min, insert, delete_max and etc.) runs in logarithm time. So it takes $O(n\log(n))$.

Of course, we can make it in a constant time through subtree augmentation!

Complete Binary Tree

Consider array as a complete binary tree being left-aligned with depth $i$ for $2^i$ nodes.
Then we need bijection between array and a complete binary tree! Moreover, We do not need pointers replacing with index!

• left($i$) = $2i+1$
• right($i$) = $2i+2$
• parent($i$) = $[{i-1 \over 2}]$

This bijection implicitly assures balanced binary tree.
Personally, I think that this can gives us an binary tree like array which take logarithm time for operations with in-place sorting!

Binary Heap

complete binary tree with Max-Heap Property

• $Q[i] \ge Q[j]$ for $j \in$ {left($i$), right($i$)}
• keeping larget elements higher in tree
• we do not know which child is bigger than the other.

Operations

• Insert

we can easily append it with constant time but to obtain Max Heap Property, we should run max_heapify_up(index $i$) which swap child with parent node and recurse it along with its ancester with logarithm time.

• Delete_max

delete max is easy but max item is root node. swap its item with that of the last node. Then we can update the order of index. Finally we get the index of max item. Then we can sustain Max Heap Property and DS.

• build

Originally, insert n items at last takes $O(n\log(n)) = \sum depth(i) = \sum \log(i) = \log(n!)$. Think of the case where brand-new item is the largest item! heapify every time insert for its resulting depth times.

Rather than starting from leaf, we can allocate the first node to brand-new item and heapify for its resulting height times. No need to search where every item is less than brand-new item.
$\sum height(i) = \sum (\log(n)-\log(i))$

Heap Sort

Takes $O(n\log(n))$ for each insert and delete_max. To run sorting, we need we need insert and delete_max for every node. That’s why it take $n$ times $\log(n)$.