Algorithms & Data Structures - Heap

A priority queue is a special type of queue where items with special characteristic are removed from the list first.

Heap is a priority queue data structure.

heap is a structure that fulfils two properties:

1.Shape (no hole)
A heap must be a complete tree.

2.Order of its element
The value stored in each node of the heap must be greater than, less than, or equal to the value of its children, depending on what type of heap it is.


Nodes in a heap are filled from left to right, and we cannot proceed to the next lower level of the tree until all nodes in that particular level are filled.


There are two types of heaps:

Ascending heap

This is a heap in which the values of the parent's nodes are smaller than or equal to the value of the children's nodes.



Descending heap

This is a heap in which the value of the parent's nodes are greater than or equal to the value of the children's nodes




Example:
Given these data: 17, 8, 12, 4, 26, 5, 14.
Build a descending and ascending Heap


BINARY HEAP

The binary heap is the classic method used to implement priority queues.

A binary heap is a binary tree that, except for the bottommost level, is completely filled from left to right.



HEAP SORT

A heapSort is a method of sorting an array of items of no particular order into an array of certain order.

Applicable to its name, this method uses a heap to facilitate sort operations.

Operations with HEAPSORT

• Insertion
• Deletion
• delete Min
• delete Max

Insertion

REHEAP UP CONCEPT

Delete Min

Coding : check previous courseware

Delete Max
Involved descending heap


Exercise 1:
Given the following numbers, build an ascending and descending heap.

8, 54, 43, 3, 77, 89, 21, 23, 5, 40

Perform deletemin for the ascending heap and deletemax for the descending heap

Exercise 2:
Use heapsort to sort the numbers into ascending list.

8, 54, 43, 3, 77, 89, 21, 23, 5, 40