classification
Title: heapq fails to sort tuples by datetime correctly
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.9, Python 3.8
process
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: Nosy List: mike.koikos, steven.daprano
Priority: normal Keywords:

Created on 2021-03-03 10:09 by mike.koikos, last changed 2021-03-03 11:15 by steven.daprano. This issue is now closed.

Files
File name Uploaded Description Edit
test_heapq.py mike.koikos, 2021-03-03 10:09 unit test proving wrong behaviour
Messages (2)
msg388012 - (view) Author: MichaƂ Kozik (mike.koikos) Date: 2021-03-03 10:09
Tuples (datetime, description) all are sorted by the date except one entry (2021-03-09) which is out of order:

        Expected order:             Actual order:
        2021-03-04 Event E          2021-03-04 Event E
        2021-03-07 Event B          2021-03-07 Event B
        2021-03-08 Event C          2021-03-08 Event C
        2021-03-09 Event A          2021-03-11 Event D
        2021-03-11 Event D          2021-03-09 Event A

In REPL it can be replicated by pasting the following code:

import heapq
from datetime import datetime

event_a = (datetime.strptime('2021-03-09', '%Y-%m-%d'), "Event A")
event_b = (datetime.strptime('2021-03-07', '%Y-%m-%d'), "Event B")
event_c = (datetime.strptime('2021-03-08', '%Y-%m-%d'), "Event C")
event_d = (datetime.strptime('2021-03-11', '%Y-%m-%d'), "Event D")
event_e = (datetime.strptime('2021-03-04', '%Y-%m-%d'), "Event E")

events = []
heapq.heappush(events, event_a)
heapq.heappush(events, event_b)
heapq.heappush(events, event_c)
heapq.heappush(events, event_d)
heapq.heappush(events, event_e)

expected_list = [event_e, event_b, event_c, event_a, event_d]

assert events == expected_list
msg388013 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2021-03-03 11:15
Heaps are not sorted lists! It is true that a sorted list is a heap, but heaps are not necessarily sorted.

Here is another heap which is not sorted:

>>> L = []
>>> for n in (9, 7, 8, 11, 4):
...     heapq.heappush(L, n)
... 
>>> L
[4, 7, 8, 11, 9]


https://en.wikipedia.org/wiki/Heap_(data_structure)


Also:

>>> L = [9, 8, 7, 2, 3, 5, 4, 1, 0, 6]
>>> heapq.heapify(L)
>>> L
[0, 1, 4, 2, 3, 5, 7, 8, 9, 6]


If we change the order of the initial values, the heap changes too:


>>> L = [9, 8, 7, 2, 3, 5, 4, 1, 0, 6]
>>> L.reverse()
>>> heapq.heapify(L)
>>> L
[0, 4, 1, 6, 5, 3, 2, 7, 8, 9]
History
Date User Action Args
2021-03-03 11:15:32steven.dapranosetstatus: open -> closed

nosy: + steven.daprano
messages: + msg388013

resolution: not a bug
stage: resolved
2021-03-03 10:09:09mike.koikoscreate