How to insert elements in a heap

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

Answer 1

[James Tursa]

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?

[Ken]

I want to insert the 4 elements into the heap and then sort them or bubble through with lower keys above the higher keys i.e. key #1 will be above key#2 etc.

[James Tursa]

Is there a reason why you are apparently coding up the sorting from scratch instead of using the MATLAB function "sort"? E.g., why can't you do this:

[~,x] = sort([ElementsToInsert.key]);  % <-- Get the indexes of the sorted result

And then use the indexing information in the variable "x" to create your sorted list all at once? E.g.,

BinMinHeap = ElementsToInsert(x);  % lhs is sorted version of rhs according to key

[Ken]

Firstly, I am not able to insert the elements into the heap; I tried this as you said but got only blanks for the other 3 elements:

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

This is what I got: BinMinHeap =

2×1 struct array with fields:

    pos
    key

BinMinHeap =

3×1 struct array with fields:

    pos
    key

BinMinHeap =

4×1 struct array with fields:

    pos
    key

[James Tursa]

This was what I intended for you with my above suggestion:

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);

I.e., I had assumed you still built the ElementsToInsert struct array as usual, then did the sorting to create the BinMinHeap.

[Ken]

When I put this in the assignment I get error "•The second element in the heap is wrong". Not sure why

[James Tursa]

I just copied and pasted this into my command window and it works fine. Are you running some other code as well?

[Ken]

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

incorrect

•The second element in the heap is wrong

[James Tursa]

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]

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

[James Tursa]

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

Answer 2

[Alexandra Harkai]

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

[Ken]

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.