2.6.3 Heap - Heap Sort - Heapify - Priority Queues

Name: 2.6.3 Heap - Heap Sort - Heapify - Priority Queues
Uploaded: 2019-03-08T20:14:37.000Z
Duration: 1 h 42 min 8 s

Heap Overview

In this video, the instructor covers the topic of heap. The subtopics include binary trees, complete binary tree, heap insertion and deletion, heap sort, and heapify. The instructor emphasizes that understanding these topics is crucial to understanding heap sort.

Representation of Binary Tree Using Array

Example of a binary tree with alphabets

Formulas for storing elements and their relationships in an array

Example of how the formulas are used to store elements in an array

Filling elements level by level automatically follows the formulas

Udemy Courses

Instructor has two courses on Udemy: C++ programming and data structures using C++ and some algorithms.

Both courses are suitable for beginners as well as advanced learners.

Courses cover all topics in detail to improve skills.

Conclusion

Heap is an important topic that requires a good understanding of binary trees, complete binary trees, heap insertion and deletion, heap sort, and heapify. The instructor's Udemy courses can help learners improve their skills in these areas.

Representation of Binary Trees

In this section, the speaker explains how to represent binary trees using formulas and arrays. They explain that the left child of a node is represented by 2i+1 and the right child is represented by 2i+2 in an array.

Binary Tree Representation

The left child of a node is represented by 2i+1 and the right child is represented by 2i+2 in an array.

If there are missing nodes, leave a blank space in the array to maintain relationships between elements.

A full binary tree has maximum number of nodes for its height, while a complete binary tree has no gaps between elements when represented in an array.

Full and Complete Binary Trees

In this section, the speaker explains what full and complete binary trees are. They define full binary trees as having maximum number of nodes for their height, while complete binary trees have no gaps between elements when represented in an array.

Full Binary Trees

A full binary tree has maximum number of nodes for its height.

If any node is added or removed from a full binary tree, it will no longer be considered as full.

Complete Binary Trees

A complete binary tree has no gaps between elements when represented in an array.

All levels except possibly the last level must be completely filled with nodes.

Another definition of complete binary trees is that they are full binary trees up to height H-1, and in the last level, elements are filled from left to right.

Examples of Complete Binary Trees

In this section, the speaker provides examples of complete and incomplete binary trees. They explain how to check if a tree is complete by checking for missing nodes at each level.

Examples

The first example provided is a complete binary tree.

The second example provided is not a complete binary tree because it has missing nodes.

The third example provided is not a complete binary tree because it does not have nodes filled from left to right in the last level.

Complete Binary Trees and Heaps

In this section, the speaker explains what a complete binary tree is and how it relates to heaps. They also introduce the concept of max heap and min heap.

Complete Binary Trees

A complete binary tree has all levels filled except possibly the last level, which is filled from left to right.

The height of a complete binary tree will be minimum, that is log n height of a.

Every node in a complete binary tree has two children except for the nodes on the last level.

Heaps

A heap is a complete binary tree that satisfies certain conditions.

In a max heap, every parent node has a value greater than its children nodes.

In a min heap, every parent node has a value smaller than or equal to its children nodes.

Duplicates are allowed in both max and min heaps.

Insertion into Max Heap

To insert an element into a max heap, add it as the last element in the array representation of the heap.

Compare the inserted element with its parent node. If it is greater than its parent node, swap them. Repeat until no more swaps are needed.

Deletion from Max Heap

To delete an element from a max heap, remove the root node and replace it with the last element in the array representation of the heap.

Compare the new root node with its children nodes. If it is smaller than either of its children nodes, swap it with the larger child node. Repeat until no more swaps are needed.

Time Complexity

The time complexity for insertion and deletion in a heap is O(log n).

Insertion and Deletion in Max Heap

In this section, the speaker explains how to insert and delete elements in a max heap. They explain that insertion involves sending the element upwards from leaf to root, while deletion can only be done on the root element.

Insertion in Max Heap

The speaker draws a tree and explains how to fill its elements after inserting an element.

The time taken for insertion is Big O of log n or order of log n, depending on the height of the complete binary tree.

The time taken for inserting one element in a heap is minimum Big O of 1 and maximum is log n.

Deletion in Max Heap

Only the root element can be deleted from a max heap without affecting its structure.

When deleting an element, it must be replaced with the last element in the complete binary tree before adjusting its position downwards towards leaf.

Adjusting elements involves comparing children of new root and swapping them if necessary until they satisfy max heap property.

Heap Sort

In this section, the speaker explains how to delete an element from a heap and maintain the max heap property. They also explain how deletion takes log n time and how deleting elements can result in a sorted list.

Deleting Elements from a Heap

To delete an element from a heap, remove the root and replace it with the last element in the complete binary tree.

Adjust the elements downwards towards leaf to form a max heap.

The direction of adjustment is different than in insertion; it's done from root towards leaf.

When you delete an element, you get the next largest element from the heap. If you keep deleting elements, you will get them in descending order.

Maintaining Max Heap Property

When comparing elements to maintain max heap property, always compare with children first before comparing with parent.

After deleting an element, there may be free space in the array. This space is not part of the heap but can be used to store deleted elements if desired.

Heap Sort

Heap sort has two steps:

Create a heap by inserting all elements one by one.

Delete all elements from the heap one by one; they will be sorted automatically.

To create a heap, start with one element and insert each subsequent element into its correct position to maintain max heap property.

Once all elements are inserted into the heap, delete them one by one to obtain a sorted list.

Heap Creation and Heap Sort

In this section, the speaker explains how to create a max-heap and perform heap sort. The time taken for inserting an element in a heap depends on the height of a complete binary tree or a heap, which is log n.

Creating Max-Heap

To create a max-heap, insert elements one by one at the next free space and move them upwards.

Compare each element with its parent until it reaches its correct position in the heap.

If an element is greater than its parent, swap them until it reaches its correct position in the heap.

Repeat these steps until all elements are inserted and we get a max-heap.

Performing Heap Sort

To perform heap sort, delete elements from the root of the max-heap one by one.

After deleting an element, replace it with the last element in the complete binary tree or heap.

Adjust downwards by comparing each child with its parent until it reaches its correct position in the heap.

Repeat these steps until all elements are deleted and sorted in ascending order.

Heap Sort

In this section, the instructor explains how heap sort works and its time complexity.

Creating a Heap

To create a heap, insert elements one by one and adjust them towards the root.

Time complexity for creating a heap is O(n log n).

Deleting Elements in Heap Sort

In heap sort, elements are deleted and stored at the free space obtained after deletion.

Time complexity for deleting an element in heap sort is O(log n).

Total time complexity for deletion in heap sort is 2n log n.

Heapify Procedure

Heapify is a procedure for creating a max-heap from an array.

The direction of adjustment in heapify is different from that of creating a heap.

Starting from the last element, scan the array from right to left and adjust each element downwards until it becomes part of the max-heap.

Time complexity for heapify procedure is O(n).

HIPAA Phi and Priority Queues

In this section, the speaker explains what priority queues are and how they work. He also discusses the advantages of using a heap data structure to implement priority queues.

Understanding Priority Queues

Priority queues are similar to FIFO (First-In-First-Out) queues, but with an added element of priority.

Elements in a priority queue are inserted with a priority value, and when deleting elements, the highest-priority element is removed first.

The value of an element itself can be its priority. For example, smaller numbers can have higher priorities than larger numbers.

Implementing Priority Queues with Heap Data Structures

A heap data structure is a better option for implementing priority queues than using a normal array because it takes less time for insertion and deletion operations.

If you want smaller numbers to have higher priorities, use a min heap. If you want larger numbers to have higher priorities, use a max heap.

Heap data structures take logarithmic time for both insertion and deletion operations, making them faster than normal arrays.

Conclusion

Using heap data structures is the best way to implement priority queues efficiently.