 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 19 Jun 2008 12:37:36 +0200, "scott" <sco### [at] scott com> wrote:
>> Most newsagents keep them behind the counter and sell as many as you
>> want, from 1 upwards.
>
>Also if you go to the cigarette/lotto counter at the front of most large
>supermarkets, they have stamps.
>
But do they sell self confidence?
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> A Min Heap is a kind of binary tree that stores data in such a way that
> retrieving the "minimum" element is an O(1) operation. Insertion and
> deletion are both O(log n), and I believe joining two heaps should be
> O(log n) as well.
> A "heap sort" involves turning something into a heap (with O(n log n)
> complexity) and then repeatedly removing the minimum element (with O(n)
> complexity) to yield a fully sorted list.
Btw, a balanced binary search tree has all those properties and then
some. Insertion and deletion are O(log n) operations, and you can not
only get the minimum but *also* the maximum element in O(1) time. Such
a tree can be used to sort a list of elements in O(n log n) time.
Moreover, the tree preserves full ordering: If so needed, you can traverse
the entire tree in O(n) steps and get all the elements in increasing order
(something you can't do with a heap). And even moreover, *searching* for
an element is an O(log n) operation (again something which cannot be done
so fast with a heap).
So the question arises: Given that a balanced binary search tree has all
the same properties as a heap, and even more, why are heaps considered
useful at all?
The answer is: Heaps don't require any ancillary data whatsoever (while
balanced binary search trees require three pointers and a flag for each
element). Moreover, the entire heap can be stored in a contiguous array
(which, as said, doesn't require *any* additional data).
This is what makes heaps more efficient than binary search trees in
many cases. For example using a binary tree for sorting an array of
elements requires O(n) amount of additional RAM, while using heap sort
requires O(1) additional memory. Same applies, for example, for a priority
queue.
Note that a heap requires random access (at least if it's used without
any ancillary data), while a binary tree doesn't. For this reason a heap
can only be used efficiently with arrays.
So this raises another question: If you are going to use a heap with
something else than an array (for example a tree structure), what are
the advantages of the heap over a regular balanced binary search tree?
The advantages of the binary tree over the heap are plenty. By constructing
a heap tree you are throwing away the one property heaps have: Space
efficiency.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> A Min Heap is a kind of binary tree that stores data in such a way that
>> retrieving the "minimum" element is an O(1) operation. Insertion and
>> deletion are both O(log n), and I believe joining two heaps should be
>> O(log n) as well.
>
> Btw, a balanced binary search tree has all those properties and then
> some. Insertion and deletion are O(log n) operations, and you can not
> only get the minimum but *also* the maximum element in O(1) time. Such
> a tree can be used to sort a list of elements in O(n log n) time.
> Moreover, the tree preserves full ordering: If so needed, you can traverse
> the entire tree in O(n) steps and get all the elements in increasing order
> (something you can't do with a heap). And even moreover, *searching* for
> an element is an O(log n) operation (again something which cannot be done
> so fast with a heap).
>
> So the question arises: Given that a balanced binary search tree has all
> the same properties as a heap, and even more, why are heaps considered
> useful at all?
I was under the impression that any kind of balanced tree tends to be
faster to access [because it's balanced, so you avoid the O(n)
worst-case behaviour], but slower to update [because you have to keep
re-balancing it]. A heap is much simpler to keep balanced because you
have far more freedom about where to put things. (On the other hand, an
in-order traversal is much slower.)
So it appears to me that the two simply have "different" properties.
Some things are more efficient with a heap, some with a balanced search
tree.
Unless you know something I don't...
> The answer is: Heaps don't require any ancillary data whatsoever (while
> balanced binary search trees require three pointers and a flag for each
> element). Moreover, the entire heap can be stored in a contiguous array
> (which, as said, doesn't require *any* additional data).
>
> So this raises another question: If you are going to use a heap with
> something else than an array (for example a tree structure), what are
> the advantages of the heap over a regular balanced binary search tree?
> The advantages of the binary tree over the heap are plenty. By constructing
> a heap tree you are throwing away the one property heaps have: Space
> efficiency.
Hmm, interesting...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> They're talking about people who have experience with Linux kernel
> development and stuff - *I* can't even *read* C.
Well, yes, OK. That's not what you said first, but OK. So find someplace
that's doing new things. Or apply anyway, and figure out how to do
interviews.
>> Quite! That's what people are trying to tell you. You explain things
>> very clearly.
>
> Well, *I* like to think I explain things very clearly. But unless other
> people actually agree with me, I have to wonder whether I'm just kidding
> myself...
Well, you're getting a lot of agreement here. What's that tell you? :-)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Huffman coding is one of those algorithms that seems delightfully
> "obvious" after you've been told the algorithm. No doubt it seemed
> highly non-obvious before anybody thought of it. ;-)
That's kind of what I was saying.
> Nah. Teaching requires social skills, not to mention a truly heroic
> level of self-confidence. I possess neither.
Note that "teaching" and "tutoring" are two separate things. To tutor,
you don't really need to be organized or deal with behavior problems in
the students or anything. You're doing pure teaching stuff, helping kids
learn what other teachers have already decided they should learn.
> I do enjoy writing about such things... but it never seems to generate
> much of a reaction. I guess I'm the only person who cares. :-(
Count the responses to your post.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Yeah, but I won't be working for Google, will I? :-P
Not if you don't apply!
> Oh, you mean that place that shuts 20 minutes before I got home? :-P
If you can't take off long enough to buy stamps, and you can't talk Gina
into getting some for you, you definitely need to switch jobs. :-)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> To be honest, I've never seen stamps on sale anywhere except at a post
> office.
Every european country I've been to, the "tobacconists" seem to deal
with all the government collect-small-sums kinds of things, like
lotteries and stamps. Maybe a tobacco shop would have them?
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> data MinHeap x = Node x (MinHeap x) (MinHeap x) | Null
This is much cleaner than anything you'd see in Erlang, fwiw. Lots of
Erlang syntax for passing around functions (or lambdas) is so
heavy-weight that making (say) a list of lambdas as a bound variable in
another lambda you pass somewhere winds you up with so much nesting and
syntax cruft you're almost required to split it into a different function.
I've found there's a couple of annoyances with functional programming
(at least in Erlang):
1) Every control-structure is out of line. You can't really do a while
loop without having the body show up somewhere else, and almost always
needing a name. (I suspect Haskell's lazy evaluation makes this much
less of a problem, since you can just use something like fold over a
multi-gigabyte file and not worry about bombing out.)
2) There's no simple way to pass private information around. If I'm
doing some process that is (say) reading thru a big file, processing
hundreds of lines a second but still taking dozens of minutes to run, if
I want to put in a counter to print how far along it has gotten every
1000 lines (so I know it's working), it's a major pain to pass and
update that everywhere, interfering with all kinds of things (including
the caller of the function needing to pass the initial counter).
3) If you have a functionality that has a complex control flow, you
basically wind up writing it as a bunch of separate functions with tail
calls routing things around, like a state machine. Every time one you
change one of those to track something new, you have to track down every
call and pass the new thing. (For example, you have a turn-based game
that has a dozen paths thru it that all lead back to the next turn. You
decide you want to keep track of each move in the game. You can't just
add a static variable and append each move to it - you have to modify a
dozen places where the function is called to pass the partial list.)
I will admit, pretty much everything worked right pretty easily once I
got it to run at all, so it isn't that difficult, but it does seem like
a maintenance problem in a big program with lots of functionality.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> only get the minimum but *also* the maximum element in O(1) time.
This needs a pointer from the root directly to the smallest leaf and
largest leaf, doesn't it? Not to dispute; I'm just trying to understand
how it's a constant-time operation. O(lg N) is easy to understand.
And by "three pointers" you're including a pointer to the parent, yes?
What's the flag? the red/black flag?
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> > only get the minimum but *also* the maximum element in O(1) time.
> This needs a pointer from the root directly to the smallest leaf and
> largest leaf, doesn't it? Not to dispute; I'm just trying to understand
> how it's a constant-time operation. O(lg N) is easy to understand.
Yes, you obviously require a pointer to the first and last nodes, but
these pointers can be kept updated at no extra cost (in other words,
keeping these pointers doesn't change the computational complexity of
any of the operations, and are very lightweight to keep updated).
Even without the pointers getting the min and max values is O(log n).
With a heap getting the max value is an O(n) operation.
> And by "three pointers" you're including a pointer to the parent, yes?
Right. (AFAIK self-balancing binary trees require the parent pointer
at each node, and they also make things like traversing the tree using
iterators much easier.)
> What's the flag? the red/black flag?
Yes. Keeping the tree balanced requires some ancillary data besides
the pointers.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
