https://docs.python.org/3/library/heapq.html

Boston University

Applications of using a heap data structure include : 

     -  Find the largest or smallest value quickly 
     -  Implement a priority queue efficiently
     -  Find the order in statistics 
     -  Implementation of Dijkstra's algorithm, Huffman encoding, and Prim's algorithm


Applications of Heap Data Structure 

A priority queue represents a collection of items where each item has a priority associated with it. A higher priority shows that an item is more '" important ".

For a min - priority queue, the highest priority item will have the smallest value. For a max - priority queue, the highest priority item will have the largest value.

Priority Queue 

Priority Queue Implementation

Dijkstra's algorithm uses a min - priority queue to find the shortest path from a node designated as the source node to all of the other nodes. It can be used to find the shortest distance from one city to another or to find the best route when using a GPS. 

Dijkstra's Algorithm

https://bradfieldcs.com/algos/graphs/dijkstras-algorithm/

Dijkstra's Algorithm 

Huffman encoding is a lossless data compression algorithm where the input characters are represented by variable length codes (Prefix codes). These codes are based on the frequency in which the character appears. More common inputs are represented by smaller codes and the lesser common inputs are represented by bigger code. To do this efficiently, it can use a min heap tree ( where the lowest frequency will have the highest priority). 

Huffman encoding is not always optimal and can be replaced by other entropy encoding forms such as arithmetic coding.

Huffman Encoding 

https://www.cs.auckland.ac.nz/software/AlgAnim/huffman.html

https://www.section.io/engineering-education/huffman-coding-python/

Huffman Encoding in Python

https://bradfieldcs.com/algos/graphs/prims-spanning-tree-algorithm/

Prim Algorithm in Python

Prim's Algorithm is a greedy algorithm ( since it chooses the most optimal next step) that finds the minimum spanning tree by adding one vertex at a time. It begins with an empty spanning tree that gets initialized with a vertex from a graph. At each step, it finds the minimum - weight edge out of the edges that are not already in the tree and moves the edge to the minimum spanning tree. 

It can use a priority queue to add a vertex to the minimum spanning tree since it is typically more efficient at finding the vertex with a minimum - weight edge than using a linked list or other data structure.

Prim Algorithm 

https://www.sciencedirect.com/science/article/pii/S0020019001002204

Learn Before

Related