restoring heap property after insertion several elements
up vote
2
down vote
favorite
Let we have a binary heap, realized by an array of length n. We write at the end of this array k elements. After that we want to restrore the heap property on this array of length n+k.
The complexity should be O(k + (logn)*log(log(n))).
My attemts. Of course we can restore the heap property of the full array with complexity O(n+k) using standart procedure. But it doesn't satisfy this complexity.
Also I have heard about the following method. Let we make a heap on the k last elements by O(k) and after that we create a "new heap" with first element greater (if we work with max-heaps) then the tops of first heap of size n and second heap of size k and with first heap as left subheap of new heap and second heap as right subheap. After that we delete top element by O(log(n+k)). But I really don't understand how to realize this approach, when we use an array representation.
arrays algorithm data-structures heap complexity-theory
asked Nov 4 at 9:51
Maxim Kuznetsov
111
New contributor
Maxim Kuznetsov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
2
down vote
favorite
Let we have a binary heap, realized by an array of length n. We write at the end of this array k elements. After that we want to restrore the heap property on this array of length n+k.
The complexity should be O(k + (logn)*log(log(n))).
My attemts. Of course we can restore the heap property of the full array with complexity O(n+k) using standart procedure. But it doesn't satisfy this complexity.
Also I have heard about the following method. Let we make a heap on the k last elements by O(k) and after that we create a "new heap" with first element greater (if we work with max-heaps) then the tops of first heap of size n and second heap of size k and with first heap as left subheap of new heap and second heap as right subheap. After that we delete top element by O(log(n+k)). But I really don't understand how to realize this approach, when we use an array representation.
arrays algorithm data-structures heap complexity-theory
asked Nov 4 at 9:51
Maxim Kuznetsov
111
New contributor
Maxim Kuznetsov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let we have a binary heap, realized by an array of length n. We write at the end of this array k elements. After that we want to restrore the heap property on this array of length n+k.
The complexity should be O(k + (logn)*log(log(n))).
My attemts. Of course we can restore the heap property of the full array with complexity O(n+k) using standart procedure. But it doesn't satisfy this complexity.
Also I have heard about the following method. Let we make a heap on the k last elements by O(k) and after that we create a "new heap" with first element greater (if we work with max-heaps) then the tops of first heap of size n and second heap of size k and with first heap as left subheap of new heap and second heap as right subheap. After that we delete top element by O(log(n+k)). But I really don't understand how to realize this approach, when we use an array representation.
arrays algorithm data-structures heap complexity-theory
asked Nov 4 at 9:51
Maxim Kuznetsov
111
New contributor
Maxim Kuznetsov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Let we have a binary heap, realized by an array of length n. We write at the end of this array k elements. After that we want to restrore the heap property on this array of length n+k.
The complexity should be O(k + (logn)*log(log(n))).
My attemts. Of course we can restore the heap property of the full array with complexity O(n+k) using standart procedure. But it doesn't satisfy this complexity.
Also I have heard about the following method. Let we make a heap on the k last elements by O(k) and after that we create a "new heap" with first element greater (if we work with max-heaps) then the tops of first heap of size n and second heap of size k and with first heap as left subheap of new heap and second heap as right subheap. After that we delete top element by O(log(n+k)). But I really don't understand how to realize this approach, when we use an array representation.
arrays algorithm data-structures heap complexity-theory
arrays algorithm data-structures heap complexity-theory
asked Nov 4 at 9:51
Maxim Kuznetsov
111
New contributor
Maxim Kuznetsov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Nov 4 at 9:51
Maxim Kuznetsov
111
New contributor
Maxim Kuznetsov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Nov 4 at 9:51
Maxim Kuznetsov
111
New contributor
Maxim Kuznetsov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Nov 4 at 9:51
Maxim Kuznetsov
111
asked Nov 4 at 9:51
Maxim Kuznetsov
111
111
New contributor
Maxim Kuznetsov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Maxim Kuznetsov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Maxim Kuznetsov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
The simplest thing would be to apply the "heap insert" operation on each of the k new elements, starting with the first. This has complexity O(k log(n)), which if k is much smaller than n is better than O(k + log(n) log(log(n)))
answered Nov 4 at 9:58
John Zwinck
147k16173285
1
Thank you. Of course I understand it. For this k should be not greater than log(log(n)). Also if k = O(n) than the approach with creating heap on all elements will be good in the complexity sense. But the most interesting situation is for an arbitrary k.
– Maxim Kuznetsov
Nov 4 at 10:23
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
The simplest thing would be to apply the "heap insert" operation on each of the k new elements, starting with the first. This has complexity O(k log(n)), which if k is much smaller than n is better than O(k + log(n) log(log(n)))
answered Nov 4 at 9:58
John Zwinck
147k16173285
1
Thank you. Of course I understand it. For this k should be not greater than log(log(n)). Also if k = O(n) than the approach with creating heap on all elements will be good in the complexity sense. But the most interesting situation is for an arbitrary k.
– Maxim Kuznetsov
Nov 4 at 10:23
add a comment |
up vote
1
down vote
The simplest thing would be to apply the "heap insert" operation on each of the k new elements, starting with the first. This has complexity O(k log(n)), which if k is much smaller than n is better than O(k + log(n) log(log(n)))
answered Nov 4 at 9:58
John Zwinck
147k16173285
1
Thank you. Of course I understand it. For this k should be not greater than log(log(n)). Also if k = O(n) than the approach with creating heap on all elements will be good in the complexity sense. But the most interesting situation is for an arbitrary k.
– Maxim Kuznetsov
Nov 4 at 10:23
add a comment |
up vote
1
down vote
up vote
1
down vote
The simplest thing would be to apply the "heap insert" operation on each of the k new elements, starting with the first. This has complexity O(k log(n)), which if k is much smaller than n is better than O(k + log(n) log(log(n)))
answered Nov 4 at 9:58
John Zwinck
147k16173285
The simplest thing would be to apply the "heap insert" operation on each of the k new elements, starting with the first. This has complexity O(k log(n)), which if k is much smaller than n is better than O(k + log(n) log(log(n)))
answered Nov 4 at 9:58
John Zwinck
147k16173285
answered Nov 4 at 9:58
John Zwinck
147k16173285
answered Nov 4 at 9:58
John Zwinck
147k16173285
answered Nov 4 at 9:58
John Zwinck
147k16173285
147k16173285
1
Thank you. Of course I understand it. For this k should be not greater than log(log(n)). Also if k = O(n) than the approach with creating heap on all elements will be good in the complexity sense. But the most interesting situation is for an arbitrary k.
– Maxim Kuznetsov
Nov 4 at 10:23
add a comment |
1
Thank you. Of course I understand it. For this k should be not greater than log(log(n)). Also if k = O(n) than the approach with creating heap on all elements will be good in the complexity sense. But the most interesting situation is for an arbitrary k.
– Maxim Kuznetsov
Nov 4 at 10:23
1
1
Thank you. Of course I understand it. For this k should be not greater than log(log(n)). Also if k = O(n) than the approach with creating heap on all elements will be good in the complexity sense. But the most interesting situation is for an arbitrary k.
– Maxim Kuznetsov
Nov 4 at 10:23
Thank you. Of course I understand it. For this k should be not greater than log(log(n)). Also if k = O(n) than the approach with creating heap on all elements will be good in the complexity sense. But the most interesting situation is for an arbitrary k.
– Maxim Kuznetsov
Nov 4 at 10:23
add a comment |
Maxim Kuznetsov is a new contributor. Be nice, and check out our Code of Conduct.
Maxim Kuznetsov is a new contributor. Be nice, and check out our Code of Conduct.
Maxim Kuznetsov is a new contributor. Be nice, and check out our Code of Conduct.
Maxim Kuznetsov is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53139543%2frestoring-heap-property-after-insertion-several-elements%23new-answer', 'question_page');
}
);
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
