41. Heaps (striver sheet)

Topics-
1. check given array is heap
2. convert max to min heap
3. Kth smallest element
4. Kth largest element
5. Top K freq elements

Extras-
1. Quick Sort
2. Bucket Sort
3. Heap Sort
-------------------------------------------------------------------------------------------------------------------------

Heaps implementation using arrays-

                       Max heap                                                                  Min Heap

   
------------------------------------------------------------
Heapify Algo : to place an element into its correct position in a binary heap 


----------------------------------------------------------------------------------------------------------------------------
1. Check if array is heap or not-

ans: use true false in heapifyDown algo, 
starting from idx 0 to last non leaf node

-----------------------------------------------------------------------------------------------------------------------------
2. Converting min to max heap:

apply heapifyDown algo from bottom to up.
start from first non leaf node


--------------------------------------------------------------------------------------------------------------------------
3. Kth largest & Kth smallest 

done in love babbar notes
--------------------------------------------------------------------------------------------------------------------------
5. Top K freq elements


Brute Force- using map and sorting

-------------------------------
Optimal- using min heap
we will build a min heap which sorts as per frequency
-----------------------------------------------------------------------------------------------------------------------------
6. K-sorted or nearly sorted

------------------------------------------------------------------------------------------------------------------------









































Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more