Power of Heap
HTML-код
- Опубликовано: 6 сен 2024
- This video explains why we should care about heap data structure.In this video, I have shown the usefulness of heap by comparing it to other available data structures like an array (sorted + unsorted) and linked list (sorted + unsorted).Heap out-performs if we need to perform a lot of find-min and find-max operations with delete-min, delete-max and insert operations.All the operations can be done in maximum of logN time and minimum of O(1) time.So, heap is a very powerful data structure if we need these common operations.
🧡 HELP us by donating on patreon: / techdose
CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
USEFUL LINKS:
🟠Must do TIPS to ACE Virtual Interview: • 🔴Must do Tips to ACE y...
🟢Best strategy to excel your coding interview: • 🔴Best strategy to exce...
🟡Get your dream job in 1 month: • 🔴Get your dream job in...
🔵How to crack dream job in just 2 months: • How to crack dream job...
🟣7 Days DSA plan: techdose.co.in...
RELATED LINKS:
Website:
Implement stack using heap: • Implement stack using ...
#heap #heapcourse #techdose
Good video, thanks. However, searching in a sorted linked list is O(n) still, as far as I understand.
Sir nice video but I feel even sorted linked list searching takes 0(N ) time not logN 7:00
If you can't have random access then it should. You may improve complexity if Linked List is implemented using nodepool.
Thank you very much for this comparisons as it lends perspective.
I wonder how one can apply binary search on linked list?!
We can't, there is no possible way to guess the position of the half of linked list in memory
Sir searching in heap will only take logn right ? Since we dont need to search everything
No, searching a random element will be linear.
your explanations are great.
How can you binary search on a sorted linked list? is it possible ?
Please feel free to correct me :)
Imagine you assign each of the reference in the linked list a specific index/order and create a separate out of place array for them, O(n) for both space and time.
Then do binary search on that new array, and refer back to the respective node in the linked list.
That's just my idea, but I can be wrong.
directly it may not be possible but while insertion you can take extra space to save the UID_address in a sorted set to apply bounded search.
If you wanna remove something then the map balances itself (self balancing BST).
If you wanna add something anywhere you will have access to adjacent node and you need to get another UID_address which fits in between the adjacent keys.
Ordering is taken care by self-balancing BST.
Since its non-trivial and requires usage of other Data Structures, hence we limit ourself to say binary search is not directly possible but saying its not possible no matter what would be an over-statement.
Hope you got it.
Really very informative ❤️ video 😊😊
Thank you so much sir 💕😊
Welcome :)
How searching in a sorted LL can be O(logN) ? you need to find the middle node which will be O(N)
exactly!
directly it may not be possible but while insertion you can take extra space to save the UID_address in a sorted set to apply bounded search.
If you wanna remove something then the map balances itself (self balancing BST).
If you wanna add something anywhere you will have access to adjacent node and you need to get another UID_address which fits in between the adjacent keys.
Ordering is taken care by self-balancing BST.
Since its non-trivial and requires usage of other Data Structures, hence we limit ourself to say binary search is not directly possible but saying its not possible no matter what would be an over-statement.
Hope you got it.
A great chain of help for student community bro. Hats off ✨
damn your way of explaining is so nice
Thanks
Are we able to apply BS on the linked list? We can not access it by index. I wonder how?
At 4:02 it’s incorrect. Inserting into a sorted array is O(logn) not O(N). Since it’s sorted you can use binary search to figure out where to do the insertion.
But after insertion you need to shift all the elements on one end by 1 position :)
@@techdose4u oh yes, your correct. Thank you sir.
@@davngo no problem :)
Sir, Using a sorted linked list, finding the min and deleting min will both have O(1) complexity. Only the insertion will have 0(n) time complexity.
So, there will be draw O(1) between heap n sorted linked list while finding min.
deletion of min value will be faster in linked list
only downside of linked list will be the insertion
is it worth to use a new data structure heap just for faster insertion ??
I am new to DSA. Please help me understand it
Yes it is totally worth it. Firstly because when you will be making big software then the amount of data that needs to be stored will reach in many GBs or maybe TBs also. So, any thing that would improve the time taken even if slightly must be done. Secondly, even though the time taken by Linked List appears to be same yet another big factor is the space that we need to use to form a linked list. In formation of a linked list we need an int data type and also a pointer that will store the address of the next block. So, this worsens the space complexity.
Can you do a video on Big O?
I already did. Please watch it in time complexity playlist.
Thanks
Welcome :)
1:06 Can someone pls explain how is this n+n = n, but not n*n = n^2? 1:54. Thanks in advance :)
i love you, you made me feel like I can code
Great ❤️
Sir, why searching takes O(N) time in heap , it's similar to BST there it take log(N) times to search ?
BST has a special property of storing values. We can make decision at any node which way to search. But heap has a different property, so we need linear search.
@@techdose4u Sir , got it. Thanks :)
Great info. Much appreciated
thank you
god level!
For creating an array to min heap takes nlogn
O(N) using build heap.
Thanks sir. Till now i thought we cant apply binary search on linkedlist. Now I got to know abt skip list. I will learn it. But the time complexity is same o(n) but u have written o(log n).
For which part are you suggesting ?
@@techdose4u in sorted linkedlist, u said that for searching it takes o(log n). But in gfg they said it is o(n)
@@poojitharavuri2943 that is through binary search
Really good sir .
Thanks :)
sir you are loocking awesome
😅
high quality content
ty sir ,ty very much
Prerequisite?
No prerequisite for this. It's the 1st video. You will understand the entire concepts once you complete all the videos starting from the next one.
Thanks Sir, I have a question.Can we apply binary search in sorted ll? 6:43
I dont think we can apply binary search in a linked list
@@aashimakansal3171 Yes
Main problem for applying Binary Search is to access any element randomly in O(1). You can use skip list for searching in optimized time in LL.
@@techdose4u Thanks sir, I have never heard about the skip list before.
@@techdose4u but binary search on ll takes O(n) time complexity , isn't it , but ya sure skip list data structure take O(logn)
Nice Videos
Thanks
How do u get this black background and bright colors ?
black magic
Hi Suriya bro,
I've one doubt. Can you please clarify for me?
Last 3 years I'm working as a manual and automation tester in Embedded Networking, somehow I entered into this domain, but I've been self-interested in coding & want to be a developer. but, in the developer interview, I don't have an experience of dev to show. I'm not getting interested to work on testing, my minds want to be a developer but not able to do. It's internally hurting me a lot. what to do? Need your suggestion, please.
You should learn and do some personal projects.
How can you apply binary search on a sorted link list? You can't index a list. Please don't give out wrong information to students.
directly it may not be possible but while insertion you can take extra space to save the UID_address in a sorted set to apply bounded search.
If you wanna remove something then the map balances itself (self balancing BST).
If you wanna add something anywhere you will have access to adjacent node and you need to get another UID_address which fits in between the adjacent keys.
Ordering is taken care by self-balancing BST.
Since its non-trivial and requires usage of other Data Structures, hence we limit ourself to say binary search is not directly possible but saying its not possible no matter what would be an over-statement.
Hope you got it.
even if the linked list is sorted , it will take O(n) time to search. its the nature of linked list , you are wrong.
directly it may not be possible but while insertion you can take extra space to save the UID_address in a sorted set to apply bounded search.
If you wanna remove something then the map balances itself (self balancing BST).
If you wanna add something anywhere you will have access to adjacent node and you need to get another UID_address which fits in between the adjacent keys.
Ordering is taken care by self-balancing BST.
Since its non-trivial and requires usage of other Data Structures, hence we limit ourself to say binary search is not directly possible but saying its not possible no matter what would be an over-statement.
Hope you got it.
@@techdose4u Since you did not mentioned that we need help from some other datastructure (BST), so i was confused.
Sir are you software at google
No
Vd
nice to see ur face for first time
:)
The Only thing missing here is Interaction with students in between explaining
Hjbb
Bbbbbbb😂😂😂😂😂😂