4 added 10 characters in body
source | link

Heapify a list

META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

Details

  • Your implementation can produce min- or max-heaps, whatever is more convenient.
  • Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, most known sorting algorithms like quicksort fail to meedmeet this requirement.

Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k

For a max heap we just replace >= with <=.

Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]

The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]

Heapify a list

META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

Details

  • Your implementation can produce min- or max-heaps, whatever is more convenient.
  • Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, most known sorting algorithms fail to meed this requirement.

Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k

For a max heap we just replace >= with <=.

Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]

The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]

Heapify a list

META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

Details

  • Your implementation can produce min- or max-heaps, whatever is more convenient.
  • Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, known sorting algorithms like quicksort fail to meet this requirement.

Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k

For a max heap we just replace >= with <=.

Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]

The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]
3 added 64 characters in body
source | link

Heapify a list

META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

Details

  • Your implementation can produce min- or max-heaps, whatever is more convenient.
  • Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, most known sorting algorithms fail to meed this requirement.

Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k

For a max heap we just replace >= with <=.

Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]

The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]

Heapify a list

META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it.

Details

  • Your implementation can produce min- or max-heaps, whatever is more convenient.

Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k

For a max heap we just replace >= with <=.

Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]

The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]

Heapify a list

META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

Details

  • Your implementation can produce min- or max-heaps, whatever is more convenient.
  • Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, most known sorting algorithms fail to meed this requirement.

Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k

For a max heap we just replace >= with <=.

Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]

The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]
2 added 176 characters in body
source | link

Heapify a list

META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it.

Details

  • Your implementation can produce min- or max-heaps, whatever is more convenient.

Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k

For a max heap we just replace >= with <=.

Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]

The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]

Heapify a list

Given a list of integers, heapify this list and return it.

Details

  • Your implementation can produce min- or max-heaps, whatever is more convenient.

Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k

For a max heap we just replace >= with <=.

Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]

The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]

Heapify a list

META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it.

Details

  • Your implementation can produce min- or max-heaps, whatever is more convenient.

Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k

For a max heap we just replace >= with <=.

Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]

The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]
1
source | link