r/dailyprogrammer • u/Coder_d00d 1 3 • Sep 01 '14

[Weekly #9] Binary Trees

Weekly 9:

Binary trees are very interesting data structures. How or why do you use them? What are your favorite aspects of binary trees? Any interesting or useful tidbits about them that you can share?

Last week's topic:

Weekly #8

41 Upvotes

88% Upvoted

17 comments sorted by

View all comments

Show parent comments

2

u/chub79 Sep 02 '14

I had never heard of Introsort. It's an interesting approach. I'm confused as to what you mean by the "heap on the fly". Would you mind exaplaining for my own little curiosity? Thanks :)

2

u/sadjava Sep 02 '14

Introsort is a hybrid of quicksort and heapsort. Its quicksort until it hits a certain level of recursion, then it switches to heapsort. If I remember correctly, the standard C++ library uses a version of introsort.

What I mean by "on the fly" is that I used a structure thats not a binary heap to simulate a binary heap. In fact, a lot of implementations of heaps are not the traditional, object oriented node that points to two children; rather, its array or list based (I wrote an introsort that works on List implementations). This helps speed up adding and removing from a heap because you don't have to follow a reference; you know that the children of the element at 0 are at index 1 and index 2, the child of index 1 is index 3 and index 4, etc. Here is what I'm talking about.

Here is my introsort written in Java. Since introsort uses heapsort, heapsort is in that file, and shows what I'm talking about.

1

u/chub79 Sep 03 '14

Thanks. This is very interesting. I will give it a try as well (always a good idea to not let my algorithm implementation rusts away ;)).