Perhaps the most dramatic algorithmic improvement made possible by using appropriate data structures occurs in sorting. Selection sort is a simple-to-code algorithm that repeatedly extracts the smallest remaining element from the unsorted part of the set:
SelectionSort(A)
For i = 1 to n do
Sort[i] = Find-Minimum from A
Delete-Minimum from A
Return(Sort)
Selection sort is typically implemented by partitioning the input
array into sorted and unsorted regions.
To find the smallest item, we perform a linear sweep through the unsorted
portion of the array.
The smallest item is then swapped with the ith item in the array
before moving on the next iteration.
Selection sort performs n iterations, where the average iteration
takes n/2 steps, for a total of 
time.
But what if we improve the data structure?
It takes O(1) time to remove a particular item from an unsorted array
once it has been located,
but O(n) time to find the smallest item.
These two are exactly the operations supported by priority queues.
So what happens if we replace the
data structure with a better priority queue
implementation, either a heap or a balanced binary tree.
Operations within the loop now take 
time each, instead of O(n).
By using such a priority queue implementation,
selection sort is sped up to 
from .
The name typically given to this algorithm, heapsort,
obscures the relationship between them, but heapsort is nothing but
an implementation of selection sort with the right data structure.