How to insert elements in a heap

Question

Ken 2016-10-31

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/309995-how-to-insert-elements-in-a-heap

评论： James Tursa 2016-11-1

I am trying to insert elements on to a heap with the code below but get error "conversion to double from struct not possible"

ElementsToInsert = [];
ElementsToInsert(1).pos = [3,1]; ElementsToInsert(1).key = 4;       
ElementsToInsert(2).pos = [3,2]; ElementsToInsert(2).key = 2;   
ElementsToInsert(3).pos = [3,3]; ElementsToInsert(3).key = 1; 
ElementsToInsert(4).pos = [4,2]; ElementsToInsert(4).key = 3;
BinMinHeap = [];
for n=1:1:length(ElementsToInsert)
    %insert ElementsToInsert(n) at the end of the heap
   BinMinHeap(n)=ElementsToInsert(n)
while BinMinHeap(n)<=BinMinHeap(n-1)
      swap(BinMinHeap(n),BinMinHeap(n-1))
      %BinMinHeap(n)=BinMinHeap(n-1)
          ...;    
      end
  end

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

James Tursa 2016-10-31

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/309995-how-to-insert-elements-in-a-heap#answer_241452

在 MATLAB Online 中打开

You can clear the variables instead of initializing them to empty doubles. E.g.

% ElementsToInsert = [];
clear ElementsToInsert  % <-- clear the variable

But then you will run into an error using the index n-1 when n=1 in your loop. So maybe make this change also:

% BinMinHeap = [];
BinMinHeap = ElementsToInsert(1);  % <-- Initialize to 1st element
for n=2:1:length(ElementsToInsert)  % <-- Starting index changed from 1 to 2

Then you will run into an error on this line for comparing structs:

while BinMinHeap(n)<=BinMinHeap(n-1)

To fix this, I don't know what you really want to compare here. Maybe the key? E.g.,

while BinMinHeap(n).key<=BinMinHeap(n-1).key

But even with this change, I have to wonder why you have this in a while loop. Are you intending to bubble the latest entry up to its appropriate spot? If so, you will need to change the indexing you use in this while loop.

Then this line looks suspicious:

swap(BinMinHeap(n),BinMinHeap(n-1))

It appears you want to swap two element of BinMinHeap, but calling a function for this likely will not do what you intend since functions in general work with copies of the inputs. Maybe you meant this?

        % swap(BinMinHeap(n),BinMinHeap(n-1))
        temp = BinMinHeap(n);
        BinMinHeap(n) = BinMinHeap(n-1);
        BinMinHeap(n-1) = temp;

Are you trying to code up a simple insertion or bubble sort?

10 个评论
显示 8更早的评论隐藏 8更早的评论

Ken 2016-11-1

No, I ran it alone. Here is what I did:

In this exercise we will develop the "insert" operation of a Binary Min-Heap. As learned during the lecture, new elements are always first added to the end of the heap (and thus the array they are stored in), and then exchanged with their parent element for as long as their "key" is smaller. Remember that elements consist of a "position-key" pair, so that positions in the map can be partially ordered according to their "key" value, which in A* corresponds to the sum of "cost so far" and an estimate of "cost to go". The figure below illustrates how the elements of an array (the storage container we will use) correspond to the entries in the heap.

Please write the "insert" function where indicated below. At the end of your code, the heap should be consistent again. 1 % the following elements are to be inserted into the heap

% binary min-heap container 9 % use the same structure as for "ElementsToInsert"

clear ElementsToInsert

ElementsToInsert(1).pos = [3,1]; ElementsToInsert(1).key = 4; ElementsToInsert(2).pos = [3,2]; ElementsToInsert(2).key = 2;

ElementsToInsert(3).pos = [3,3]; ElementsToInsert(3).key = 1;

ElementsToInsert(4).pos = [4,2]; ElementsToInsert(4).key = 3;

[~,x] = sort([ElementsToInsert.key]);

BinMinHeap = ElementsToInsert(x);

incorrect

•The second element in the heap is wrong

James Tursa 2016-11-1

编辑：James Tursa 2016-11-1

在 MATLAB Online 中打开

First, I don't understand this statement by you:

"The second element in the heap is wrong"

Because here is the exact output I get with the code:

>> [ElementsToInsert.key]
ans =
     4     2     1     3     <-- Original key ordering
>> [BinMinHeap.key]
ans =
     1     2     3     4     <-- Sorted order looks correct
>> reshape([ElementsToInsert.pos],2,4)'
ans =
     3     1     <-- Original ordering of pos data
     3     2
     3     3
     4     2
>> reshape([BinMinHeap.pos],2,4)'
ans =
     3     3     <-- New order follows the new sorting as expected
     3     2
     4     2
     3     1

Looks good to me. So you need to explain to me why you think this is incorrect.

Second, I asked this question earlier:

"Is there a reason why you are apparently coding up the sorting from scratch instead of using the MATLAB function "sort"?"

Your answer to that question should have been "yes", because your homework problem apparently is asking you to specifically write some "bubble insertion" code. So forget all of that "sort" function stuff I wrote since it doesn't fit the assignment (even though I still think it is correct). Apparently you are being asked to write a loop that builds the sorted output one-by-one by adding an element to the end and then bubbling it up to the appropriate spot. E.g., if you put everything together that we have been talking about on creating this "bubble up" code:

% some data to add
clear ElementsToInsert
ElementsToInsert(1).pos = [3,1]; ElementsToInsert(1).key = 4;       
ElementsToInsert(2).pos = [3,2]; ElementsToInsert(2).key = 2;   
ElementsToInsert(3).pos = [3,3]; ElementsToInsert(3).key = 1; 
ElementsToInsert(4).pos = [4,2]; ElementsToInsert(4).key = 3;
% now build the sorted output one by one
BinMinHeap = ElementsToInsert(1);  % initialize to 1st element
for n=2:length(ElementsToInsert)  % add the rest of the elements one-by-one
    BinMinHeap(n) = ElementsToInsert(n);  % add ElementsToInsert(n) at the end of the heap
    k = n;  % index to keep track of current location of added element
    while BinMinHeap(k).key < BinMinHeap(k-1).key  % if k'th key is smaller than (k-1)'th key
        temp = BinMinHeap(k);  % swap the k'th element with (k-1)'th element (both pos and key)
        BinMinHeap(k) = BinMinHeap(k-1);
        BinMinHeap(k-1) = temp;
        k = k - 1;  % decrement k to point to new position of added element
        if( k == 1 )  % if k'th element is at the top, then stop bubbling this element
            break;
        end
     end
end

I have posted a solution for you (at least as far as I understand the assignment) because (1) You have clearly been writing code and trying to understand this, (2) You were somewhat close to a solution with your attempts, and (3) You have been at it for awhile now and are probably frustrated (my belated Happy Halloween treat to you).

Ken 2016-11-1

Can't thank you enough - Halloween Treat and all! Will try this and let you know - Regards

James Tursa 2016-11-1

(I've been eating my kid's Halloween candy today and feel generous)

请先登录，再进行评论。

Answer 2

Alexandra Harkai 2016-10-31

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/309995-how-to-insert-elements-in-a-heap#answer_241451

在 MATLAB Online 中打开

BinMinHeap(n)=ElementsToInsert(n)

does not work because of this. You can write instead:

BinMinHeap(n)=deal(ElementsToInsert(n))

However, there will be problems with this still, because the comparison is not a valid operation on structs:

BinMinHeap(n)<=BinMinHeap(n-1)

so you could compare the keys instead:

BinMinHeap(n).key<=BinMinHeap(n-1).key

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Ken 2016-10-31

I want to insert the 4 elements into the heap and then sort them based on their keys i.e. lower keys above higher keys.

请先登录，再进行评论。

How to insert elements in a heap

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

10 个评论
显示 8更早的评论隐藏 8更早的评论

更多回答（1 个）

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

另请参阅

类别

标签

Community Treasure Hunt

How to insert elements in a heap

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

10 个评论 显示 8更早的评论隐藏 8更早的评论

更多回答（1 个）

1 个评论 显示 -1更早的评论隐藏 -1更早的评论

另请参阅

类别

标签

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

10 个评论
显示 8更早的评论隐藏 8更早的评论

1 个评论
显示 -1更早的评论隐藏 -1更早的评论