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

Imagens e arquivos do mapa