Wrox Programmer Forums

Need to download code?

View our list of code downloads.

Register | FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read
BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 3rd Edition
This is the forum to discuss the Wrox book Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition by John Mongan, Noah Kindler, Eric Giguere; ISBN: 978-1-118-26136-1
Welcome to the p2p.wrox.com Forums.

You are currently viewing the BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 3rd Edition section of the Wrox Programmer to Programmer discussions. This is a community of tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developers’ questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
DRM-free e-books 300x50
Reply
 
Thread Tools Display Modes
  #1 (permalink)  
Old March 20th, 2016, 12:13 PM
Registered User
Points: 18, Level: 1
Points: 18, Level: 1 Points: 18, Level: 1 Points: 18, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Mar 2016
Posts: 4
Thanks: 0
Thanked 0 Times in 0 Posts
Default Binary tree to heap in O(N)

Page 75, there is this problem :

Quote:
You are given a set of integers in an unordered binary tree. Use an array sorting routine to transform the tree into a heap that uses a balanced binary tree as its underlying data structure.
Then, it is stated :

Quote:
Because you both start and end with binary tree data structures, transforming into an array probably isn’t the most efficient way to accomplish the end goal. You might comment to your interviewer that if not for the requirement to use an array sorting routine, it would be more efficient to simply heapify the nodes of the starting tree: that is, reorder them such that they meet the criteria of a heap. You can heapify the tree in O(n) time, while just the array sort is at least O(n log(n)).
This heapify algorithm in O(N) is never explained, and I simply don't see how it works...
Reply With Quote
  #2 (permalink)  
Old July 11th, 2017, 10:37 AM
Wrox Author
Points: 21, Level: 1
Points: 21, Level: 1 Points: 21, Level: 1 Points: 21, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Oct 2012
Posts: 8
Thanks: 0
Thanked 0 Times in 0 Posts
Default

It's a little counterintuitive, but the standard heapify algorithm is O(n). Essentially this is because you don't actually need to do an O(log n) operation on every element. Much more detailed discussion and analysis here: https://stackoverflow.com/questions/...ime-complexity

John
Reply With Quote
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
heap x stack Robson BOOK: Professional C++, 2nd Edition 1 June 3rd, 2014 01:21 PM
Heap of typing errors HELP!!! ours All Other Wrox Books 11 December 24th, 2007 10:23 AM
Heap Monitor pallavi11 VB How-To 5 January 11th, 2007 07:37 PM
Could not reserve enough space for object Heap overcit Apache Tomcat 0 February 23rd, 2006 11:11 AM
Binary Search Tree mehdi62b General .NET 1 September 10th, 2004 03:01 AM



All times are GMT -4. The time now is 03:08 PM.


Powered by vBulletin®
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.