Re: printing nodes of a bst using the min heap property?

From: Richard Harter (cri_at_tiac.net)
Date: 10/15/04 

Date: Fri, 15 Oct 2004 10:28:06 GMT

On Fri, 15 Oct 2004 09:23:55 +0000 (UTC), Willem <willem@stack.nl>
wrote:

>CBFalconer wrote:
>) <snip: discussion about printing the leaves of a BST in sorted order>
>)
>) Sorting takes O(NlnN). Heaping doesn't.
>
>As a completely off-the mark tangent:
>
>You can sort an array by inserting all the items into a binary search
>tree, and then traversing the tree. How fast would such an algorithm
>be, compared to the more traditional sorting methods ?

Oddly enough, it has much the same properties as quicksort, albeit
somewhat slower because of the greater complexity of the logic.

Relevant Pages

  • Re: Limitation of os.walk
    ... events during such a tree traversal. ... # Python 1.1 ... strip the cmp option from sort in Python 3. ... key-based sorting is simpler than cmp-based ...
    (comp.lang.python)
  • Re: Q: sorts key and cmp parameters
    ... flattened list of comparison values or the tree itself can be cast ... easily transformable to a key function, I think your best bet is to ... I don't hate sorting in py3.x. ... I don't subscribe to the cult of the real-world use case. ...
    (comp.lang.python)
  • Re: sorts with binary trees
    ... Sure you can do sorting with a binary search tree. ... But this isn't necessarily a good way to sort a set of values. ... quicksort, are likely to be actually faster in practice. ...
    (comp.programming)
  • Re: If you were inventing CoBOL...
    ... >in the unbalanced tree while you're sorting. ... >putting the logic in a library called by the SORT verb. ... >>encourage to code up double linked lists and tree traversals? ...
    (comp.lang.cobol)
  • Re: Binary Search Tree Vs Quick Sort
    ... one is an algorithm and one is a data structure. ... Sorting is appropriate if you have a fixed set of data, and you need it in some specific order. ... The binary tree is appropriate if you are trying to _maintain_ a collection of data and you want it to _always_ be in sorted order. ... Another difference is that with a sort, you don't have much opportunity to avoid the worst-case scenarios. ...
    (comp.lang.java.programmer)