Hello!!! Could I ask you something about an algorithm?

Hey, what's up?

@Axoren Fine, thanks... and you? :)

I'm alright. You had a question?

@Axoren So do we have to have a heap with $k$ positions, put the elements of the first positions of the $k$ lists in the heap, heapify and delete the root, which will be the smallest element, and put it into the new list, then place at the root the second element from the list from which the minimum was, then heapify and continue the same procedure?

Could you refresh my memory on the amortized costs of reheap?

Or what you're calling "heapify"

Looks like it's $O(h)$ where $h$ is the height of the heap

So, @evinda That procedure wouldn't necessarily produce a sorted list.

Consider $k$-reverse order lists.

The largest elements will be put into the heap of size $k$

Wait...

Ignore all of that, I missed this part of your question:

>merges $k$ sorted lists into one sorted list

Hmm, if the $k$-lists are sorted, then you're good with that solution because we never run into that problem.

And you end up reheapifying exactly $n-k$ times.

Well, $+1$, maybe.

@Axoren A ok... k isn't known... So if we give the lists as arguments do we have to write something like that: Algorithm(L1,L2,.....,Lk) ?

@evinda It doesn't matter if $k$ is known. What you are sure of is that $k \le n$

Which means you can safely say that your algorithm is still $O(n \log k)$

Because it's rough amortized cost is $(n - k)\log k$

@Axoren I meant that we have either to give the lists as argument at the function or declare them, or not?

Do you have to write the algorithm in a language? Or just describe it in pseudocode?

@Axoren In a pseudocode

Then you have some ultimate freedom here.

You can simply describe list $i$ as $L_i$ or $L[i]$

So could I give them at the algorithm as arguments as follows? L1,L2,...,Lk ?

And then elements $j$ in those lists as $L_i[j], L[i][j], L_{i,j}$

You can pass in a set of lists, instead.

Or a list of lists, rather.

Algorithm(L)

For example

@Axoren Since L1,....,Lk are lists, we consider them as pointers, right?

@evinda Yes, which is why we can assume that the amortized cost of accessing those lists by their $k$-value is $O(1)$, and indexing each of those lists is also $O(1)$.

But since it's pseudocode, you don't need to go into the low-level stuff too deeply.

@Axoren So do we to declare at the beginning k pointers so that the lists remain unchanged?

If you have any depth of list of lists, accessing any element by it's exact "coordinates" is $O(1)$

You can also do some things like "treat the $k$ lists as Stacks with a pop function"

And you don't need to even talk about them as memory structures.

They're just objects with $O(1)$ functions that let you interact with them.

@Axoren A ok.. but if we consider that the lists are pointers, do we declare at the beginning k pointers?

There should be no need to do that.

Doing so won't hurt in any way.

Well, actually, if you're professor is a stickler for it, then maybe you should mention they're pointers.

But in pseudocode, you assume that the implementations of the objects you use are optimal.

Otherwise, accessing values in a list could be $O(n)$ like in a linked list.

@Axoren And how can we put the elements of the lists at the heap?

Define a heap $H$ and append elements to it.

It's essentially just a list with two functions $Heapify$ and $RemoveMin$

@Axoren So do I have to write a function that appends elements to a heap?

If you've been presented one in class, you can simply address it by name

In the same way that you don't have to write an implementation for lists.

You know such a function exists because you've seen implementations before and they're generally accepted.

Like heapify and RemoveRoot

Or do we append elements to a heap with an other function?

Heap Insert does both Heapifying and Adding

So use that

@Axoren So should I use the function that I sent you?

Yeah

@Axoren There the one argument is a heap table, but we do not have one.... :/

Define one

$H$ is an empty heap table

Pseudocode can just be sentences

@Axoren Then at this heap table we have to put the first elements of the k sorted lists, right? How could we do this?

You can iterate over each of the lists, can't you?

Because you have a list of them

If we consider them as pointers we can't, can we? @Axoren

Yes, we can.

Create a list of pointers that contains them all

$L = [L_1, L_2, L_3, ..., L_k]$

@Axoren So we consider that L is an array that contains all the lists?

Yup, that works.

But honestly, it's pseudocode, each of your statements can be english sentences

Sorry, I'm bouncing around doing things

From your algorithm, you only create a list with one element.

@Axoren I have to go for a while... I will be back in one hour...

@Axoren What could I change? :/

First, what is your output variable?

And what should it be?

Right.

"@Axoren So do we have to have a heap with $k$ positions, put the elements of the first positions of the $k$ lists in the heap, heapify and delete the root, which will be the smallest element, and put it into the new list, then place at the root the second element from the list from which the minimum was, then heapify and continue the same procedure?"

Let's start by turning this into pseudocode, then.

Everything you said in that sentence, is a statement in pseudocode.

Pseudocode doesn't follow a specific syntax or grammar

As long as its understood.

So, first thing you mentioned is create a $k$-sized heap.

Next, you go one at a time through each of the lists, and add the first element to the heap.

Once the heap is full, you take the root, which is going to be the first element of the output list.

@Axoren In order to create a k-sized heap, do we use the following function?

BUILD-HEAP(A)
    heapsize := size(A);
    for i := floor(heapsize/2) downto 1
        do HEAPIFY(A, i);
    end for
END

Yes, assume that you have access to the Build-Heap function.

No need to supply it.

Now, after you pick the first element of the new list, what do you do?

@Axoren So before calling the function, we have to fill the Heap table, right?

Yes, because HEAPIFY uses the contents to restructure the table as a heap.

I have to depart in half an hour.

Sorry ahead of time if I have to up and disappear abruptly

@Axoren A ok... :)

If L[1] is the first list, then L[1][1] is the first element of the first list.

The heap doesn't have to be in any order before you build the heap.

We can live in a much better world than that. Consider references instead.

Rather than being a pointer, it's a reference.

We can talk about L[1] as if it were the list itself

rather than a pointer

It leads to a cleaner reading and the meaning is obvious.

Very rarely do we want the memory locations of things in pseudocode.

@Axoren If we consider that L[1] is the first list, how can we distinguish its elements?

With another set of brackets.

L[i][j], for example.

This would read as the j'th element of the i'th list in L.

So can we create the heaptable  as follows?

for (i=1; i<=k; i++){
     H[i]=L[i];
     i++;
} @Axoren

Yes, as long as you're sure not to increment i twice.

Why should we increment it twice? @Axoren

You shouldn't but you did. :P

@Axoren Oh yes right :D

And once you've done this and turned the list into a heap, what's the next thing you do?

Then we call the function BUIL-HEAP(H), right? @Axoren

Right, but after this?

@Axoren Then we will have to put at the first position of a new list the minimum element, right?

Right. There's a point of failure that will happen right after this.

Once you remove the minimum element, what do you do next?

We will have to put at the root the second element of the list from which the minimum element was, right?

And then heapify

Let's consider an example: L[1] = {1, 1, 1}; L[2] = {2, 2, 2}

The heap will contain {1, 2} after the first loading of it.

Once you remove the min element, the heap contains {2}

@Axoren Don't we then have to insert the next 1 from L[1] and then heapify so that 1 is at the root and can be deleted as the second element?

What do you do next here?

Right.

Instinctively, you determined that we had to add the next element from L[1]

This is because that's where the min element came from before

In this case, we wouldn't use HeapDelete.

HeapDelete reheaps

So we have to write an other function, right? @Axoren

Instead, we can simply take the root element and replace it with its replacement, treating it like a regular list.

We know that the first element of the heap will be at location H[1]

We can just pull it right off the heap as a list.

@Axoren So it has be like that: LNEW[1][1]=H[1]; H[k]=H[1]; Heapify(H); right?

Is LNEW the name of your output list?

Yes

Why is it two-dimensional?

It should just be something like LNEW[1]

Oh yes, right... So should it be like that? LNEW[1]=H[1]; H[k]=H[1]; Heapify(H); @Axoren

Something like that.

Yeah

That works.

But we could use do it in a while-loop so that we create the whole new list, right? @Axoren

Yup

But in this while loop, you have to keep track of which list to replenish the heap from.

And what to do when a list is empty.

Alright, I need to leave.

But that's the entirety of it.

Just be careful with those edge cases and your algorithm's right.

Ok, I will try to finish the algorithm and I will send it to you... :)

I'll stay subscribed to this chat and I might be able to check it later or tomorrow.

Nice, thank you :) @Axoren