Heaps and Heapsort

Heaps and Heapsort

1. Heap

   • Despite the traditional definition, heap is not a disordered pile of items
     • Rather, it is a clever, partially ordered data structure that is especially suitable for implementing priority queues.
       • priority queue is a multiset of items with an orderable characteristic called an item’s priority
         • It has the following operations:
           • finding an item with the highest (i.e., largest) priority
           • deleting an item with the highest priority
           • adding a new item to the multiset
     • A heap can be defined as a binary tree with keys assigned to its nodes, one key per node, provided the following two conditions are met
       • Shape property—the binary tree is complete, i.e., all its levels are full except possibly the last level, where only some rightmost leaves may be missing.
       • The parental dominance or heap property—the key in each node is greater than or equal to the keys in its children.
       • Here is a list of important properties of heaps:
         • There exists exactly one essentially complete binary tree with n nodes. Its height is equal to ⌊log2 n⌋.
         • The root of a heap always contains its largest element.
         • A node of a heap considered with all its descendants is also a heap.
         • A heap can be implemented as an array by recording its elements in the top- down, left-to-right fashion

2. Heapsort

   • Is a sorting two-stage algorithm that works as follows.
     • 1- (heap construction): Construct a heap for a given array
     • 2- (maximum deletions): Apply the root-deletion operation n−1 times to the remaining heap.
     • As a result, the array elements are eliminated in decreasing order
       • since under the array implementation of heaps an element being deleted is placed last, the resulting array will be exactly the original array sorted in increasing order

Bilder und Dateien der Mindmap