Heap

Applications

Application 1

 Given a vector of integers. Sort the values in the vector in ascending order.
Input file: sort.in
Line 1: n - the number of elements in the array
Line 2: A1 - The element number1 from the array [...]
Line n+1: An - The element number n from the array
Output file: sort.out
Line 1: S1 ... Sn, where S is the array A sorted in ascending order
Restrictions
-30000<=A1, ..., An<=30000
-1<=n<=30000

Organize the vector as a heap and extract the minimum value one by one. In this way, the total complexity will be [n log n] independent of the structure of the input data.

Introductory Notions

  1. Trees
  2. Binary trees
  3. Heaps

Min-Heap generator

Heap

  1. Creation
  2. Insert node
  3. Combination
  4. Extract node

Priority queue

Applications

Dictionary

Application 2

 A graph is given by the edge list. Write a program that determines the minimum cost partial tree. The cost of a tree means the sum of the costs of the edges in the tree.
Input file: apm.in
Line 1: n m - the number of nodes or edges in the graph
Line 2: X1 Y1 C1- there is edge between nodes X1 și Y1 of cost C1 [...]
Line m+1: Xm Ym Cm- there is edge between nodes Xm și Ym of cost Cm
Output file: apm.out
Linia 1: S1 D1[...]
Linia n-1: S(n-1) D(n-1), whare Si Di represents the edge description i from the tree (The order in which they appear does not matter).

Use Kruskal's algorithm by organizing edge costs into a heap.


Application 3

 A graph is given by the list of edges and two vertices from the graph. Determine the minimum cost path between the two given vertices. The cost of a path means the sum of the costs of the edges belonging to the road.
Input file: drum.in
Line 1: n m - the number of nodes or edges in the graph
Line 2: X1 Y1 C1- there is edge between nodes X1 and Y1 of cost C1 [...]
Line m+1: Xm Ym Cm- there is edge between nodes Xm and Ym of cost Cm
Line m+2: S D - the two vertices for which the minimum path must be calculated.
Output file: drum.out
Line 1: C- minimum travel cost.

Use Dijkstra's algorithm by optimizing the search for the minimum value at a given step. To be able to extract the minimum over time [log n] organize the vector of temporary values as a heap.


Proposed Problems:

Easy:

 1.Dijkstra
2.Kruskal
3.C. Heap Operations
4.506. Relative Ranks

Medii:

 1.Ramen
2.Cezar1
3.Numar6

Dificile:

 1.Volum
2.Catmin
3.Pitici1
4.862. Shortest Subarray with Sum at Least K
5.F. Heaps