d2jsp
Log InRegister
d2jsp Forums > Off-Topic > Computers & IT > Programming & Development > Python - Min Heep
Add Reply New Topic New Poll
Views: 257Replies: 8Track Topic
Member
Posts: 8,407
Joined: Jan 29 2008
Gold: 450.00
#1
Oct 5 2012 08:01pm
Can anyone help with implementing amin heap

input heapify([[1], [2], [3], [5], [4]])

AndI get [[1], [2], [3], [5], [4]]

HoweverI want [[1], [2], [3], [4], [5]]

Code
def sift_down(heap, pos):


 end = len(heap)-1 #len
 spos = pos    #start position

 childpos = 2*pos    

 
 while spos * 2 + 1 <= end:
             child = spos * 2 + 1
             rightchild = spos * 2 + 2
             if rightchild  <= end and heap[child][0] > heap[rightchild][0]:
                 child += 1
               
             
             if child <= end and heap[spos][0] > heap[child][0]:
                 heap[spos][0], heap[child][0] = heap[child][0], heap[spos][0]
                 spos = child
               
                 
             else:
             
                 return heap



def heapify(heap): #min heap

 i = (len(heap)) // 2

 while (i > -1):
   
   sift_down(heap, i)
   
   i = i - 1
 return heap



I'm sure its a two second fix but I've been playing around with it for ages, and I don't want a 0 at the start of the heep as a dummy any help is much appreciated!!

This post was edited by BadKiwi on Oct 5 2012 08:17pm
Member
Posts: 32,925
Joined: Jul 23 2006
Gold: 3,804.50
#2
Oct 5 2012 08:20pm
can you explain whats wrong with 1 2 3 5 4? that looks perfectly valid to me, unless i'm mistaken
Member
Posts: 8,407
Joined: Jan 29 2008
Gold: 450.00
#3
Oct 5 2012 08:27pm
Quote (carteblanche @ Oct 6 2012 02:20am)
can you explain whats wrong with 1 2 3 5 4? that looks perfectly valid to me, unless i'm mistaken


OMG I have just spent the last 3 hours on this lmao and its right hahaha, oh god thanks so much!!!

Wow im an idiot!

one other problem,

that I can't seem comprehend unless I use Type()

If I was to feed in say heapify([(5,), (4,), (3,), (2,), (1,)])

how would I get it to output [(1,), (2,), (3,), (5,), (4,)]

and also still work for lists

input heapify([[1], [2], [3], [5], [4]])

And get [[1], [2], [3], [5], [4]]

So basically I can input Tuples or Lists and get an output in the format inputed;

Would I have to use Type() everywhere?

This post was edited by BadKiwi on Oct 5 2012 08:28pm
Member
Posts: 13,630
Joined: Dec 4 2009
Gold: 0.00
#4
Oct 5 2012 11:11pm
Quote (BadKiwi @ Oct 5 2012 07:27pm)
OMG I have just spent the last 3 hours on this lmao and its right hahaha, oh god thanks so much!!!

Wow im an idiot!

one other problem,

that I can't seem comprehend unless I use Type()

If I was to feed in say heapify([(5,), (4,), (3,), (2,), (1,)])

how would I get it to output [(1,), (2,), (3,), (5,), (4,)]

and also still work for lists

input heapify([[1], [2], [3], [5], [4]])

And get [[1], [2], [3], [5], [4]]

So basically I can input Tuples or Lists and get an output in the format inputed;

Would I have to use Type() everywhere?


You would just extract the iteration and return a modified object of what was passed to the function. You really just need to make this script more Pythonic. Use for-in loops instead of clunky while loops that rely on indexing instead of an iterator object.

Code
for item in heap:
   # do work on item
   # this allows you to use 'item' instead of using heap[index]
Member
Posts: 32,925
Joined: Jul 23 2006
Gold: 3,804.50
#5
Oct 5 2012 11:17pm
Quote (BreakPoint @ Oct 6 2012 01:11am)
You would just extract the iteration and return a modified object of what was passed to the function. You really just need to make this script more Pythonic. Use for-in loops instead of clunky while loops that rely on indexing instead of an iterator object.

Code
for item in heap:
   # do work on item
   # this allows you to use 'item' instead of using heap[index]


when writing a heap? how do you plan on getting the children/parent from a particular item without using the index?
Member
Posts: 13,630
Joined: Dec 4 2009
Gold: 0.00
#6
Oct 5 2012 11:58pm
Quote (carteblanche @ Oct 5 2012 10:17pm)
when writing a heap? how do you plan on getting the children/parent from a particular item without using the index?


From the looks of the input, you're iterating through a list of lists, or a list of tuples.

The first for loop loops through each iterable, which is the parent, yes? To get to the children of that iterable, just use another for loop*.

*since it looks like only the zeroth item is being retrieved, you don't really have to do another for loop.
Member
Posts: 32,925
Joined: Jul 23 2006
Gold: 3,804.50
#7
Oct 6 2012 12:03am
Quote (BreakPoint @ Oct 6 2012 01:58am)
From the looks of the input, you're iterating through a list of lists, or a list of tuples.

The first for loop loops through each iterable, which is the parent, yes? To get to the children of that iterable, just use another for loop*.

*since it looks like only the zeroth item is being retrieved, you don't really have to do another for loop.


im not reading his code. i assume the 0 you're referring to is just because he doesn't know how to use 1 array (as opposed to array of arrays).

are you familiar with heaps? ignoring offsets, a child of position i is at index i *2 or i * 2 + 1, so i'm not sure how a second for loop will help you get that when you dont know anyone's index

This post was edited by carteblanche on Oct 6 2012 12:05am
Member
Posts: 13,630
Joined: Dec 4 2009
Gold: 0.00
#8
Oct 6 2012 12:09am
Quote (carteblanche @ Oct 5 2012 11:03pm)
im not reading his code. i assume the 0 you're referring to is just because he doesn't know how to use 1 array (as opposed to array of arrays).

are you familiar with heaps? ignoring offsets, a child of position i is at index i *2 or i * 2 + 1, so i'm not sure how you plan on getting that without using the index.


Perhaps he is purposefully passing a list of lists to the heapify function, but yes, that is right.

I am not. In that case, what I said wouldn't work. Lucky for the OP, lists and tuples are treated the same when iterating or indexing. Have you actually tried passing a list of tuples to the function yet?
Member
Posts: 8,407
Joined: Jan 29 2008
Gold: 450.00
#9
Oct 6 2012 02:21am
omg this is driving me nuts ill pay people in decent uswest d2 nl gear to do an assignment (its level 1 basic stuff, as long as you know min heaps you should be fine), should only take 30 mins id guess.... I get it perfect and then something else stumps me.

Lmk if anyones keen

Or a FG amount

This post was edited by BadKiwi on Oct 6 2012 02:23am
Go Back To Programming & Development Topic List
Add Reply New Topic New Poll

© 2003-2026 d2jsp  Contact