AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Build Heap And Heapsort Without Array

Ein Thema von sk.Silvia · begonnen am 1. Mai 2006 · letzter Beitrag vom 13. Mai 2006
Antwort Antwort
Benutzerbild von sk.Silvia
sk.Silvia

Registriert seit: 8. Feb 2006
Ort: Slovenia
90 Beiträge
 
Delphi 7 Personal
 
#1

Build Heap And Heapsort Without Array

  Alt 1. Mai 2006, 15:44
hi there i would like to know how to build a heap and heapsort without using an array (i found many alghortims, but they are all using array representation of heap)

thanks
  Mit Zitat antworten Zitat
Benutzerbild von DGL-luke
DGL-luke

Registriert seit: 1. Apr 2005
Ort: Bad Tölz
4.149 Beiträge
 
Delphi 2006 Professional
 
#2

Re: Build Heap And Heapsort Without Array

  Alt 1. Mai 2006, 16:42
A heap can be very easily organized into an array, but if you use binary heaps, this type should be able to help you:

Delphi-Quellcode:
type
  PHeapNode = ^THeapNode;
  THeapNode = record
    Parent,Left,Right: PHeapNode;
    Value: Integer;
  end;
With this you should be able to build a heap:

Delphi-Quellcode:
function RandomHeap(depth: Integer; BaseNode: PHeapNode = nil): THeapNode
var i: Integer;
begin
if (BaseNode = nil) then
  begin
    Result := New(THeapNode)
  end
else
  begin
    Result := BaseNode;
    Result.Value := random(100);
  end;

if depth > 0 then
  begin
    Result.Left := New(THeapNode);
    Result.Left.Parent := BaseNode;
    ReandomHeap(depth-1,Result.Left);
   
    Result.Right := New(THeapNode);
    Result.Left.Parent := BaseNode;
    RandomHeap(depth-1,Result.Right);
  end;
end;

procedure MaxSort(Heap: THeapNode);
begin
// too lazy to write that now xD
end;
maybe I left out some pointer conversions, but that should be it.
And don't forget to free all memory you assign!
(When you make the record a class, you can implement this in the class)
Lukas Erlacher
Suche Grafiktablett. Spenden/Gebrauchtangebote willkommen.
Gotteskrieger gesucht!
For it is the chief characteristic of the religion of science that it works. - Isaac Asimov, Foundation I, Buch 1
  Mit Zitat antworten Zitat
Benutzerbild von sk.Silvia
sk.Silvia

Registriert seit: 8. Feb 2006
Ort: Slovenia
90 Beiträge
 
Delphi 7 Personal
 
#3

Re: Build Heap And Heapsort Without Array

  Alt 1. Mai 2006, 19:01
you are 17? nice

hmm. your alghoritm is nice, but cause of random(100) it wont produce a heap (child can have higher value then parent)

but ok, lets say i have a binar tree and will rebuild it to a heap, what then?
  Mit Zitat antworten Zitat
Benutzerbild von DGL-luke
DGL-luke

Registriert seit: 1. Apr 2005
Ort: Bad Tölz
4.149 Beiträge
 
Delphi 2006 Professional
 
#4

Re: Build Heap And Heapsort Without Array

  Alt 1. Mai 2006, 20:01
i didn't say it produced a sorted heap, which in your case would be a MAX-Heap, right?

well, isn't a binary tree just about the same thing? You're right, I'm just 17, and I only took a glance at wikipedia to get the structure of a binary heap.

The rest is merely pointer acrobatics...

Just looked at wikipedia again... "a heap is an abstract data structure, mostly based on trees" (rough translation )

So what does your tree look like? Is it just unsorted?

EDIT: btw, the "too lazy to write that now" comment above should not suggest that i understand heapsorting in any way (well, it does, but honestly I don't know - well, wikipedia educates)

EDIT: OK, I think I got it about now - we need a heap that maintains its (existing) order so we can just pick out the biggest element one after the other.

EDIT: and yes, there are sources saying a heap is a binary tree which is sorted.

As I just feel like it, I'll outline a simple heap class based on THeapNode. Stand By

EDIT: Well, I'll try it's not that easy. But it should be rather easy to make a (balanced, sort of) binary tree into a sorted heap. Just take the lowest leaf and check if its value is less than its parent's value. if it is, check the next leaf. if it is not, swap them.
Lukas Erlacher
Suche Grafiktablett. Spenden/Gebrauchtangebote willkommen.
Gotteskrieger gesucht!
For it is the chief characteristic of the religion of science that it works. - Isaac Asimov, Foundation I, Buch 1
  Mit Zitat antworten Zitat
tigerman33

Registriert seit: 30. Jul 2005
Ort: München
423 Beiträge
 
Delphi 2005 Professional
 
#5

Re: Build Heap And Heapsort Without Array

  Alt 1. Mai 2006, 21:05
Hi,

if you already have a binary tree, you should be able to transform it into a heap by successively performing a so-called sift operation on the nodes from the bottom up. A sift operation means exchanging the given node with the tree root. Then if necessary, you exchange that node with the larger one of its two sons to keep the ordering. After that, recursively repeat on the just-changed subtree, until the node is at its correct position.
If I remember right, it should actually be enough to do this on only the bottom half of the tree, but I'm not going to give you any guarantuee on that one...

I would suspect Wikipedia has an article on this operation, given that there seems to be one on the heapsort algorithm itself.

Hope this helped.
Christian
Der Computer hilft mir, Probleme zu lösen, die ich ohne Computer nicht hätte.
  Mit Zitat antworten Zitat
tigerman33

Registriert seit: 30. Jul 2005
Ort: München
423 Beiträge
 
Delphi 2005 Professional
 
#6

Re: Build Heap And Heapsort Without Array (Sift-operation)

  Alt 2. Mai 2006, 08:03
Wikipedia article explaining heapsort/sift:
Zitat von Wikipedia:
Code:
function sift(a, start, count) {
     var int root := start, child

     while root * 2 + 1 < count { 
         child := root * 2 + 1 // Ignore this--you can access a node's children much easier! :)

         if child < count - 1 and a[child] < a[child + 1] // Choose the larger of the sons, if there are two

             child := child + 1

         if a[root] < a[child] // If root node is too small...
             swap(a[root], a[child]) // Swap it with the previously determined larger son
             root := child // ...and keep track of where it is now.
               // This way, on the next loop iteration the subtree that has the just-moved node as its root will be sifted into
               // Another possible way here would have been to use recursion
         else
             return
     }
 }
PS: Yeah, I know this isn't really C-code. Just wanted the syntax highlighting...
Christian
Der Computer hilft mir, Probleme zu lösen, die ich ohne Computer nicht hätte.
  Mit Zitat antworten Zitat
Benutzerbild von sk.Silvia
sk.Silvia

Registriert seit: 8. Feb 2006
Ort: Slovenia
90 Beiträge
 
Delphi 7 Personal
 
#7

Re: Build Heap And Heapsort Without Array

  Alt 12. Mai 2006, 16:28
so ok, i have this code :

Delphi-Quellcode:
  procedure TBinTree.BuildHeap;
      begin
      if not(Left=nil) then
        begin
        if Left.Value>Value then
          begin
          Exchange(Left,Self);
          BuildHeap;
          end;
        Left.BuildHeap;
        end;
      if not(Right=nil) then
        begin
        if Right.Value>Value then
          begin
          Exchange(Right,Self);
          BuildHeap;
          end;
        Right.BuildHeap;
        end;
      end;
it works fine, but only just with one bug, it exchanges bad the values by the tree root (it dont makes just one exchange, the rest of the tree is ok)

somebody has an idea how to fix it?
  Mit Zitat antworten Zitat
tigerman33

Registriert seit: 30. Jul 2005
Ort: München
423 Beiträge
 
Delphi 2005 Professional
 
#8

Re: Build Heap And Heapsort Without Array

  Alt 12. Mai 2006, 19:10
Hi Silvia,

I'm not sure if this will solve your problem, but if I read your code right you neglect to determine which one is the larger of the child nodes before you swap with the root. That might look something like this:

Delphi-Quellcode:
procedure TBinTree.BuildHeap;
var Larger: TBinTree;
begin
  // Lazy evaluation of boolean expressions needs to be switched on for this to work
  Larger := Left;
  if not Assigned(Larger) then
    Larger := Right else
    if Assigned(Right) and (Left.Value < Right.Value) then
      LargerSon := Right;

  if Assigned(Larger) and (Value < Larger.Value) then begin
    Exchange(Larger,self);
    Larger.BuildHeap;
  end;
end;
If that doesn't do it, we'll need to look again.
Christian
Der Computer hilft mir, Probleme zu lösen, die ich ohne Computer nicht hätte.
  Mit Zitat antworten Zitat
Benutzerbild von sk.Silvia
sk.Silvia

Registriert seit: 8. Feb 2006
Ort: Slovenia
90 Beiträge
 
Delphi 7 Personal
 
#9

Re: Build Heap And Heapsort Without Array

  Alt 13. Mai 2006, 19:51
thanks for helping

aoup it actualy dont work right...

but when i cal my method 2 times after itself, like :
BinTree.BuildHeap;
BinTree.BuildHeap;

it makes a good heap

its not neccessary to call it more times, cause the heap is created and the output will be the same

but thats not the right way:/, it dont handle good the main root point
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 18:38 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz