40. Heaps (Luv Babbar)

Note-

1. complete BT has all levels filled except last level & nodes are filled from left to right

2. a complete BT with last level being filled is called a perfect BT

3. complete BT has a heap order property

4. max-heap: children have smaller value than parent node, always

5. min-heap: children have larger value than the parent node, always


In a 1-indexed complete BT :-

6. parent of a node is at (i/2)th index

7. left child is at (2*i) index & right child at (2*i + 1 ) for a node at idx i

8. leaf nodes are from n/2 to nth indices

In a 0-based indexing array-

left child at 2i+1 & right child at 2i+2 index of node at i-th index

last non-leaf node is at (n-2)/2 ⭐ or ( (n/2) -1 )


9. insertion & deletion : logN 

10. accessing max/min element : O(1)

11. time to build a heap-  O(n)

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

insertion in max heap-
----------------------------------------------------------------------------------------------------------------------------

Deletion of root element from max heap-
-----------------------------------------------------------------------------------------------------------------------------
Heapify Algo-(down)
used to position a node into its correct position into a heap

we don't need to process leaf nodes

this function converts tree from i-th node to leaf node, into a heap

----------------------------------------------------------------------------------------------------------------------------
Heap-Sort :-
(nlogn)
1st last ko swap kro ==> size km krke (size-1 take waalo ko) heapify m bhejde ==> repeat

given array:    70,60,55,45,50
1st iteration:   50,60,55,45,   70
2nd iteration:  60,50,55,45,   70
3rd iteration:   45,50,55,        60,70
4th iteration:   55,50,45,        60,70
5th iteration:   50,45              55,60,70
6th iteration:   45                   50,55,60,70

--------------------------------------------------------------------------------------------------------------------------
PRIORITY QUEUE-
in pq, we can access max/min element in O(1) and can do insertion or deletion in O(logn)

Max heap version of pq stores largest element at top

Min heap version of pq stores smallest element at top
----------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
1. Finding Kth largest element in an array-
Method 1:(nlogn)
sort the array & return element at reqd idx

Method 2: (nlogn + klogn) ~ nlogn
push all n elements into a priority queue then pop out (k-1) elements and .top is my answer
pushing/ popping each element takes logn time

Method-3: (nlogk)
instead of building full heap, we just build heap of size k

1. make a min heap of size k of first k elements of the array
2. now for every remaining elements of the array, replace it with top element of heap, only if it is larger

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




























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